Город: Санкт-Петербург Новосибирск Казань Язык: Русский English

Основы вычислимости и теории сложности
Санкт-Петербург / осень 2014, посмотреть все семестры

Запишитесь на курс, чтобы получать уведомления и иметь возможность сдавать домашние задания. Для записи требуется регистрация на сайте.
Перейти к регистрации Войти

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

Дата и время Занятие Место Материалы
10 сентября
18:30–19:50
Лекция 1, Лекция ПОМИ РАН Нет
10 сентября
20:00–21:20
Практика, Семинар ПОМИ РАН Нет
17 сентября
18:30–19:50
Лекция 2, Лекция ПОМИ РАН Нет
17 сентября
20:00–21:20
Практика, Семинар ПОМИ РАН Нет
24 сентября
18:30–19:50
Лекция 3, Лекция ПОМИ РАН Нет
24 сентября
20:00–21:20
Практика, Семинар ПОМИ РАН Нет
01 октября
18:30–19:50
Лекция 4, Лекция ПОМИ РАН Нет
01 октября
20:00–21:20
Практика, Семинар ПОМИ РАН Нет
08 октября
18:30–19:50
Лекция 5, Лекция ПОМИ РАН Нет
08 октября
20:00–21:20
Практика, Семинар ПОМИ РАН Нет
22 октября
18:30–20:00
Лекция 6, Лекция ПОМИ РАН Нет
22 октября
20:00–21:20
Практика, Семинар ПОМИ РАН Нет
29 октября
18:30–20:00
Лекция 7, Лекция ПОМИ РАН Нет
29 октября
20:00–21:20
Практика, Семинар ПОМИ РАН Нет
05 ноября
18:30–19:50
Лекция 8, Лекция ПОМИ РАН Нет
05 ноября
20:00–21:20
Практика, Семинар ПОМИ РАН Нет
12 ноября
18:30–19:50
Лекция 9, Лекция ПОМИ РАН Нет
12 ноября
20:00–21:20
Практика, Семинар ПОМИ РАН Нет
19 ноября
18:30–19:50
Лекция 10, Лекция ПОМИ РАН Нет
19 ноября
20:00–21:20
Практика, Семинар ПОМИ РАН Нет
26 ноября
18:30–20:00
Лекция 11, Лекция ПОМИ РАН Нет
26 ноября
20:00–21:30
Практика, Семинар ПОМИ РАН Нет
03 декабря
18:30–20:00
Лекция 12, Лекция ПОМИ РАН Нет
03 декабря
20:00–21:20
Зачет, Семинар ПОМИ РАН Нет
10 декабря
18:30–19:50
Экзамен, Лекция ПОМИ РАН файлы