Какие задачи можно решать на компьютере, а с какими компьютер не справится? Какие задачи можно решать эффективно, а какие нельзя? Из первой части курса, которая посвящена вычислимости, можно будет узнать: как доказывается алгоритмическая неразрешимость задач, доказательство и применения теоремы о неподвижной точке, арифметическую иерархию и доказательство первой теоремы Геделя о неполноте. Вторая часть курса будет посвящена сложности вычислений, кроме классических вещей (классы P,NP, сводимость, NP-полнота) мы изучим полиномиальную иерархию, булевы схемы, вероятностные алгоритмы, интерактивные протоколы и вероятностно проверяемые доказательства.

Основная литература:

• Н.К. Верещагин, А. Шень, Вычислимые функции.
• S. Arora, B. Barak, Computational Complexity: A modern approach.

Дополнительная литература:

• M. Sipser, Introduction to the theory of computation.
• Ch. Papadimitriou, Computational Complexity.
• А. Китаев, А. Шень, М. Вялый. Классические и квантовые вычисления.

Примерный план курса:

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

2. $ m $-сведения, другие примеры неразрешимых множеств. Последовательность Шпеккера. Теорема Успенского-Райса. Теорема Клини о неподвижной точке. Программа, печатающая свой текст. Доказательство теоремы Клини для искусственного языка программирования. Главные универсальные функции. Вывод теоремы Успенского-Райса из теоремы Клини.

3. Машины Тьюринга. Неразрешимость проблемы равенства слов в полугруппе (выводимости в одностороннем и двустороннем ассоциативном исчислении). Предикатные формулы (формулы I-го порядка). Интерпретации.

4. Выразимость в арифметике. Арифметичность графика вычислимой функции. Арифметическая иерархия. Универсальные множества в арифметической иерархии. Строгость арифметической иерархии. Теоремы Тарского и Геделя.

5. Недетерминированные машины Тьюринга. Определения класса NP. Примеры. Сведения по Карпу. Понятние полноты. Полнота задачи об ограниченной остановке. Полнота задачи SAT и 3-SAT.

6. NP-задачи поиска. Сведения по Куку. Сведение задач поиска к задачам распознавания. Оптимальный алгоритм для NP-задач поиска. Класс PSPACE и полная задача в ней. Теорема Ладнера о не NP-полном языке в классе NP.

7. Теоремы об иерархии по времени. Полиномиальная иерархия. Простейшие свойства, полные задачи в $ \Sigma_i^P $ и в $ \Pi_i^P $. Оракульное определение полиномиальной иерархии.

8. Булевы схемы. Вычисления с подсказкой. Класс P/poly. Включение P в P/poly. Существование функций большой схемной сложности. Теорема Карпа-Липтона. Языки большой схемной сложности в полиномиальной иерархии (теорема Каннана).

9. Вероятностная машина Тьюринга. Классы BPP и RP. Лемма Шварца-Зиппеля и вероятностный тест равенства двух многочленов. Понижение ошибки в классе BPP, BPP содержится в P/poly, BPP содержится в $ \Sigma_2 $.

10. Интерактивные протоколы. Примеры: интерактивный протокол для неизоморфизма графов и для квадратичных невычетов. Теорема Шамира (IP = PSPACE) и ее следствия.

11. Приближенные алгоритмы для задачи MAXSAT и минимальном вершинном покрытии. Вероятностно проверяемые доказательства. Формулировка PCP-теоремы. Эквивалентные формулировки.

12. Попарно-независимые хеш-функции. Лемма Вэлианта-Вазирани. Вычисления с ограничениями и по времени, и по памяти. Нижняя оценка для SAT.