\documentclass[12pt]{article}
\usepackage{amssymb,amsmath,amstext}

\newcounter{вопрос}
\newcommand{\вопрос}{\par\smallskip\refstepcounter{вопрос}\theвопрос. }
\newcommand{\R}{\mathbb{R}}

\begin{document}

\textbf{Программа курса ``Сложность вычислений" 2002
(дополнительное образование
на мехмате).}

\bigskip

\вопрос Время и память (зона) как меры сложности
вычислений.

\вопрос Полиномиальная эквивалентность по времени одноленточных и
многоленточных машин Тьюринга.

\вопрос Класс P функций, вычислимых за полиномиальное время.
Принадлежность классу P функций сложения, умножеия и деления
целых чисел, и функции возведения в степень по данному модулю.

\вопрос Теорема о иерархии для зонной сложности.

\вопрос Теорема о иерархии для временной сложности.

\вопрос Класс NP. NP-полные проблемы.
Принадлежность к NP множества простых чисел

\вопрос   Теорема Кука --- Левина
об NP-полноте проблемы выполнимости булевых
формул.

\вопрос NP-полнота задач
3-КНФ, 3-РАСКРАСКА, КЛИКА, ВЕРШИННОЕ ПОКРЫТИЕ,	
ГАМИЛЬТОНОВ ЦИКЛ, РЮКЗАК, КОММИВОЯЖЕР,
ЦЕЛОЧИСЛЕННОЕ ЛИНЕЙНОЕ ПРОГРАММИРОВАНИЕ.

\вопрос Вероятностный алгоритм распознавания простоты чисел.

\вопрос Класс BPP.

\вопрос Класс P/poly, и вложение классов P и BPP в класс
P/poly.

\вопрос Полиномиальные игры с конечным числом ходов и
полиномиальная иерархия.

\вопрос  Полиномиальные игры с полиномиальным числом ходов и
класс PSPACE.
Вложение классов полиномиальной иерархии в класс
PSPACE.

\вопрос PSPACE-полнота задачи об истинности булевых формул с кванторами.

\вопрос Вложение класса BPP в класс $\Sigma_2$ полиномиальной иерархии.

\вопрос Интерактивное доказательство неизоморфности данных графов.

\вопрос Класс IP языков, имеющих интерактивную дедуктику.
Вложение IP в класс PSPACE

\вопрос Понижение вероятности ошибки в интерактивных доказательствах
без увеличения количества раундов.

\вопрос Вложение MA[2] в AM[2].
Здесь AM[2] обозначает
класс языков, имеющих интерактивное доказательство с открытыми
бросаниями в один раунд --- сначала делает сообщение Артур, затем Мерлин.
Через MA[2] обозначается класс языков, имеющих интерактивное доказательство
в один раунд --- сначала Мерлин, затем Артур.

\вопрос Вложение класса AM[const] в класс AM[2]

\вопрос Вложение PSPACE в класс  IP.

\вопрос Вероятностно проверяемые доказательства и PCP-теорема
(без доказательства).

\вопрос Невозможность быстрого приблизительного вычисления
размера максимальной клики в данном графе (если P не равно NP).

\вопрос Доказательство с нулевым разглашением изоморфности данных
графов.

\вопрос Доказательство с нулевым разглашением раскрашиваемости
данного графа в три цвета.

\вопрос Надежные и непредсказуемые генераторы псевдослучайных битов.
Эквивалентность этих понятий.

\вопрос Построение надежного генератора $n \rightarrow p(n)$
на основе надежного генератора $n \rightarrow n+1$.

\вопрос  Необратимые функции, необратимые перестановки.
Построение непредсказуемого генератора $n \rightarrow n+1$
на основе необратимой перестановки.



\bigskip
Для сдачи экзамена достаточно решить следующие задачи.

\вопрос Доказать NP-полноту следующей проблемы.
Условие: конечное множество $A$, функция $s$ из $A$ в множество
натуральных чисел.
Вопрос: можно ли разбить $A$ на два непересекающихся
подможества $A_1,A_2$ так, чтобы
$\sum_{a\in A_1}s(a)=\sum_{a\in A_2}s(a)$.

\вопрос Доказать NP-полноту следующей проблемы.
Условие: конечное множество $A$, функция $s$ из $A$ в множество
натуральных чисел, и два натуральных числа $m,n$.
Вопрос: можно ли разбить $A$ на $m$ непересекающихся
подможеств $A_1,\dots,A_m$ так, чтобы
длина в $\R^m$ вектора $\langle\sum_{a\in A_i}s(a),i=1,\dots,m\rangle$
не превосходила $n$: $\sum_{i=1}^m(\sum_{a\in A_i}s(a))^2\le n^2$.


\вопрос Доказать NP-полноту следующей проблемы.
Условие: граф $G=(V,E)$,
подмножество $W\subset V$ и натуральное число $n$.
Вопрос: существует ли поддерево в $G$, содержащее все вершины из
$W$ и имеющее не более $n$ ребер.


\вопрос Докажите, что класс
AM[2] вложен в класс $\Pi_2=\text{co-}\Sigma_2$ полиномиальной иерархии.

\вопрос Придумайте интерактивное доказательство того, что данная формула
общезначима (то есть истинна при всех значениях переменных).

\вопрос Докажите, что если существует надежный генератор $n\to n+1$,
то существует и необратимая функция.

\bigskip

{\bf Литература.}

1. M.  Гэри, Д. Джонсон.
Вычислительные машины и труднорешаемые задачи.
М.: Мир, 1982.

2. A. Китаев, А. Шень, М. Вялый. Классические и квантовые вычисления.
М.: МЦНМО, ЧеРо, 1999.

3. Введение в криптографию. Под общей редакцией В.В.Ященко. ---
3-е изд. доп. --- М.: МЦНМО: "ЧеРо", 2000. --- 288 с.

4. М.И. Анохин, Н.П.Варновский, В.М.Сидельников, В.В. Ященко.
Криптография в банковском деле. М.: МИФИ, 1997.

5.	   L.Babai, ``Trading group  theory  for  randomness''.  Proc.
	 17th ACM Symp. on Theory of Comp. (1985), pp.421-429.


6. A. Shamir. IP=PSPACE. Journ. of the ACM, 39 (1992) 869--877.

7. O. Goldreich. Foundation of Cryptography. Basic Tools.
Cambridge UP. 2001.

8. Т. Кормен, Ч. Лейзерсон, Р. Ривест. Алгоримты: построение и анализ.
М.: МЦНМО, 2001.

\end{document}