City: Saint Petersburg Novosibirsk Kazan Language: Русский English

Foundations of computability and complexity theory
Saint Petersburg / autumn 2014, посмотреть все семестры

Enroll in the course to get notifications and to be able to submit home assignments.
Register to enroll now Login

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

Date and time Class|Name Venue|short Materials
10 September
18:30–19:50
Лекция 1, Lecture ПОМИ РАН No
10 September
20:00–21:20
Практика, Seminar ПОМИ РАН No
17 September
18:30–19:50
Лекция 2, Lecture ПОМИ РАН No
17 September
20:00–21:20
Практика, Seminar ПОМИ РАН No
24 September
18:30–19:50
Лекция 3, Lecture ПОМИ РАН No
24 September
20:00–21:20
Практика, Seminar ПОМИ РАН No
01 October
18:30–19:50
Лекция 4, Lecture ПОМИ РАН No
01 October
20:00–21:20
Практика, Seminar ПОМИ РАН No
08 October
18:30–19:50
Лекция 5, Lecture ПОМИ РАН No
08 October
20:00–21:20
Практика, Seminar ПОМИ РАН No
22 October
18:30–20:00
Лекция 6, Lecture ПОМИ РАН No
22 October
20:00–21:20
Практика, Seminar ПОМИ РАН No
29 October
18:30–20:00
Лекция 7, Lecture ПОМИ РАН No
29 October
20:00–21:20
Практика, Seminar ПОМИ РАН No
05 November
18:30–19:50
Лекция 8, Lecture ПОМИ РАН No
05 November
20:00–21:20
Практика, Seminar ПОМИ РАН No
12 November
18:30–19:50
Лекция 9, Lecture ПОМИ РАН No
12 November
20:00–21:20
Практика, Seminar ПОМИ РАН No
19 November
18:30–19:50
Лекция 10, Lecture ПОМИ РАН No
19 November
20:00–21:20
Практика, Seminar ПОМИ РАН No
26 November
18:30–20:00
Лекция 11, Lecture ПОМИ РАН No
26 November
20:00–21:30
Практика, Seminar ПОМИ РАН No
03 December
18:30–20:00
Лекция 12, Lecture ПОМИ РАН No
03 December
20:00–21:20
Зачет, Seminar ПОМИ РАН No
10 December
18:30–19:50
Экзамен, Lecture ПОМИ РАН files