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

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

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

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

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

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

Время и место (с 23 января): понедельник, 18:10, корпус на Покровском бульваре, аудитория R207. ВРЕМЯ И МЕСТО ПРОВЕДЕНИЯ БУДЕТ УТОЧНЯТЬСЯ НА ПЕРВОМ ЗАНЯТИИ

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

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

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

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

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

История

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

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

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

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

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

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

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

13 марта 2023. Занятие 8. Сертификатная сложность, чувствительность, блочная чувствительность. Гипотеза Карпа. Тернарные функции. Конспект

20 марта 2023. Занятие 9. Информационная энтропия. Конспект

11 апреля 2022. Занятие 10. Неравенство Ширера. Теорема Кана о независимых множествах. Конспект

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

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

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

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

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

Наборы задач

• Вычислимость, дедлайн 11 марта.
• Приближённые алгоритмы, дедлайн 25 марта.
• Булев анализ, дедлайн 8 апреля.
• Сложностные характеристики булевых функций, дедлайн 22 апреля.
• Информационная энтропия, дедлайн 6 мая.

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

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

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

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

• Л. А. Левин. Универсальные задачи перебора (1973). (Внушительный список комбинаторных задач с доказательствами их NP-полноты)

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

• Alexander A. Razborov & Steven Rudich. Natural Proofs

• U. Feige & Sh. Jozpeh. Separation between estimation and approximation (Классика приближённых алгоритмов: разделение по сложности задач нахождения оценки и нахождения приближённого решения)

• M. Goldmann, J. Hastad & A. Razborov. Majority gates vs. general weighted threshold gates (Фундаментальная, но простая для понимания статья по булевым схемам)

• J. Hastad. On the Size of Weights for Threshold Gates (Результат, схожий с предыдущим, только с доказательством конкретной оценки)

• R. Moser & G. Tardos. A constructive proof of the general Lovasz Local Lemma (Фундаментальная вещь из вероятностных алгоритмов (которую, кстати, планировал рассказывать Дмитрий Александрович на курсе ТВиМС))

• C. Gotsman & N. Linial. The equivalence of two problems on the cube (Один из кусков так называемой "гипотезы о чувствительности", её связь с максимальной степенью подграфа булева куба)

Литература

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. (Невероятно качественная книга про булев анализ)