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

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

\begin{document}

\textbf{Программа курса ``Сложность вычислений" 2006.}

\bigskip

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

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

\вопрос Теорема Фишера--Рабина.

\вопрос Классы P/poly, n.u.P, их равнообъемность и
вложение класса P в класс n.u.P.

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

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

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

\вопрос Теорема: если $NP\subset n.u.P$, то 
$PH=\Sigma_2$.

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

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

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

\вопрос $\#P$-полнота задачи о вычислении перманента булевой матрицы.

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

\вопрос Класс BPP. Уменьшение вероятности ошибки и
вложение класса BPP в класс
P/poly.

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

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

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

\bigskip

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

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

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

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

\end{document}