Теория вычислений 2022

Факультатив представляет собой введение в, пожалуй, центральную подобласть теоретической информатики, а именно в теорию вычислений. Данную науку можно противопоставить всем известной теории алгоритмов. Цель алгоритмического подхода -- придумать максимально быстрое решение для отдельно взятой задачи. Теория вычислений же исследует общие подходы к построению эффективного решения или, что не менее важно, доказывает его отсутствие. Для данной постановки задачи были введены так называемые сложностные классы, в том числе всем известные P и NP, задача взаимосвязи которых объявлена одной из семи Millennium Prize Problems.

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

Общая информация

Официальное название: «Теория вычислений».

Преподаватель: Павел Захаров, телеграм: @DuckBinLaden, Анна Енгоян, телеграм: @yaognennaya

Время и место (с 31 января): понедельник, 16:20, корпус на Покровском бульваре, аудитория R406.

Телеграм-чат: ссылка.

Таблица с результатами: ссылка.

Примерная программа

Из обязательных тем предполагаются первые 3 ± 1, после чего планируется сделать гибкую программу, учитывающую пожелания слушающих.

• Временная сложность, классы P и NP [пройдено].
• NP-трудные и NP-полные задачи, NP-полнота некоторых задач [пройдено].
• Space complexity, PSPACE-полные задачи [пройдено].
• Сложность вычислений с помощью схем из функциональных элементов, класс P/poly.
• Разрешающие деревья. Гипотеза Аандераа—Карпа—Розенберга.
• Коммуникационная сложность.
• Булев анализ. Теорема Эрроу.
• Спектральный экспандер. Зиг-заг произведение. Детерменированный алгоритм для задачи UPATH.
• Линейное программирование. Метод исключения переменных. Метод эллипсоидов. Симплекс-метод [частично пройдено].
• Аппроксимационные алгоритмы. ЛП релаксация для задачи MIN-VC. ЛП релаксация для задачи MAX-CUT [пройдено].
• Вероятностная сложность, класс BPP (и другие), вероятностные алгоритмы проверки числа на простоту и проверки полиномов на равенство.
• Апериодические замощения. Плитки Вана.

История

31 января 2021. Занятие 1. Машина Тьюринга. Классы P и NP. Конспект

7 февраля 2021. Занятие 2. Классы NP-hard и NP-complete. Теорема Кука-Левина. Конспект

14 февраля 2021. Занятие 3. Space complexity, space hierarchy theorem. Конспект

21 февраля 2021. Занятие 4. Линейное программирование. Приближённые алгоритмы, MAX-IND, TSP. Конспект

28 февраля 2021. Занятие 5. ЛП релаксации, MIN-VC, MAX-SAT. Конспект

7 марта 2021. Занятие 6. Разложение булевой функции в ряд Фурье: существование и единственность. Конспект

14 марта 2021. Занятие 7. Функции голосования. Теорема Эрроу. Конспект

Правила оценивания

Оценка складывается из двух пунктов:

• Задачи. Решать и сдавать задачи из нижеприведённого списка. Сдачу планируется проводить только лишь устную. Сдавать можно любому из (двоих) преподавателей. Время и место выбирается по договорённости.

• Экзамен. Экзамен будет в формате мини-конференции. Каждый студент выбирает статью из нижеприведённого списка и делает по ней доклад (минут на ДЛИНА_ПАРЫ / ЧИСЛО_СДАЮЩИХ).

Итоговая оценка формируется как O_{итоговая} = 0,7 * O_{задачки} + 0,3 * О_экз.

Наборы задач

• Вычислимость, дедлайн 15 марта.
• Приближённые алгоритмы, дедлайн 22 марта.
• Булев анализ, дедлайн 2 апреля.

Интересные статьи

Пока что заранее заготовленные примеры, список будет пополняться (учитывая предпочтения слушающих).

• J. Hartmanis & R. E. Stearns. On the complexity of algorithms (1965). (Статья, с которой началась теория сложности вычислений).

• Stephen A. Cook. The complexity of theorem-proving procedures (1971). (Определение полноты (осторожно: не совсем такое, как у нас) и теорема Кука-Левина).

• Richard M. Karp. Reducibility among combinatorial problems (1972). (Внушительный список комбинаторных задач с доказательствами их NP-полноты).

• Л. А. Левин. Универсальные задачи перебора (1973). (Примерно про то же in Soviet Russia)

• M. Agrawal, N. Kayal & N. Saxena. PRIMES is in P (2004). (Полиномиальный алгоритм проверки числа на простоту)

• Alexander A. Razborov & Steven Rudich. Natural Proofs

• S. Goldwasser & M. Sipser. Private Coins versus Public Coins in Interactive Proof Systems (Открытые случайные биты (почти) не хуже, чем закрытые)

• O. Goldreich et al. On Completeness and Soundness in Interactive Proof Systems (Распознавание x \in L с вероятностью 1 для систем интерактивных доказательств)

Литература

1. Dexter C. Kozen. Theory of Computation. (Замечательная книга по теории сложности вычислений, малоизвестная, по непонятным причинам, в нашей стране. Изложение структурировано в виде "лекций", часть из которых "обычные", а часть "продвинутые")
2. Michael Sipser. Introduction to the Theory of Computation (Очень хороший вводный учебник)
3. Михаил Вялый. Черновик учебника по приближённым алгоритмам.
4. Ryan O’Donnell. Analysis of boolean functions. (Невероятно качественная книга про булев анализ)