Вопросы к экзамену
Для сдачи экзамена надо ответить на 5 вопросов: в двух вопросах надо дать определение, в двух вопросах надо сформулировать теорему и в последнем вопросе надо рассказать доказательство теоремы. При подготовке доказательства теоремы можно пользоваться рукописными конспектами. При подготовке ответа на первые четыре вопроса конспектами пользоваться нельзя.
Определения
Многоленточные машины Тьюринга, время и память.
РАМ (равнодоступные адресные машины), время, количество использованных регистров,
длина машинного слова. Полиномиальные алгоритмы. Класс P.
Сводимости Карпа и Кука.
Определение класса NP.
Определение NP трудной и полной задачи.
Схемы из функциональных элементов, схемная сложность функций.
Класс n.u.P. Вероятностные машины Тьюринга.
Классы BPP и FBPP. Полиномиальная иерархия. Класс PSPACE.
Формулировки теорем.
Моделирование многоленточных машин Тьюринга на РАМ.
Оценка сложности выполнения арифметических операций на машинах Тьюринга.
Моделирование РАМ на машинах Тьюринга.
Теоремы о иерархии по памяти и по времени.
Теорема Фишера — Рабина.
Теорема Левина — Кука об NP полноте задачи CIRCUIT-SAT.
NP полнота задачи 3-CNF.
NP полнота задач КЛИКА, НЕЗАВИСИМОЕ МНОЖЕСТВО, ВЕРШИННОЕ ПОКРЫТИЕ,
СУММА ПОДМНОЖЕСТВА, 3-РАСКРАСКА, ГАМИЛЬТОНОВ ЦИКЛ, КОММИВОЯЖЁР.
Экспоненциальная верхняя оценка сложности любой функции. Экспоненциальная
нижняя оценка сложности некоторых булевых функций.
Теорема об уменьшении ошибки вероятностного полиномиального алгоритма.
Включение BPP в nuP. Полные задачи в классах полиномиальной иерархии.
Включение полиномиальной иерархии в PSPACE. Включение BPP в Сигма-2.
Доказательства.
Моделирование многоленточных машин Тьюринга на РАМ.
Оценка сложности выполнения арифметических операций на машинах Тьюринга.
Моделирование РАМ на машинах Тьюринга.
Теоремы о иерархии по памяти и по времени.
Полиномиальность алгоритма Эвклида. Свойства сводимостей Карпа и Кука.
Теорема Левина — Кука об NP полноте задачи CIRCUIT-SAT.
NP полнота задачи 3-CNF.
NP полнота задач КЛИКА, НЕЗАВИСИМОЕ МНОЖЕСТВО, ВЕРШИННОЕ ПОКРЫТИЕ,
СУММА ПОДМНОЖЕСТВА, 3-РАСКРАСКА, ГАМИЛЬТОНОВ ЦИКЛ, КОММИВОЯЖЁР.
Экспоненциальная верхняя оценка сложности любой функции. Экспоненциальная
нижняя оценка сложности некоторых булевых функций.
Включение P в n.u.P.
Теорема об уменьшении ошибки вероятностного полиномиального алгоритма.
Вероятностный алгоритм проверки полиномиальных алгебраических
тождеств. Включение BPP в nuP,
Полные задачи в классах полиномиальной иерархии.
Включение полиномиальной иерархии в PSPACE.
Включение BPP в Сигма-2.
Рекомендуемая литература.
0. В.Н. Крупский. Введение в сложность вычислений. М.: Факториал, 2006, 128 с.
1. А. Китаев, А. Шень, М. Вялый. Классические и квантовые вычисления. М.: МЦНМО, 1999, 192 с.
2. Ахо А., Хопкрофт Дж., Ульман Дж. Построение и анализ вычислительных алгоритмов. М. Мир 1979.
3. Кормен Т., Лейзерсон Ч., Ривест Р. Алгоритмы: Построение и анализ. М.: МЦНМО, 2001. — 960 с.
4. Гэри М., Джонсон Д. Вычислительные машины и труднорешаемые задачи. М.: Мир, 1982, 416 с.
5. Сэвидж Джон Э. Сложность вычислений. М.: Факториал, 1998. — 368 с.