Просмотр исходного текста страницы Факультатив "Теория вычислений" (Весна 2021)

Факультатив представляет собой введение в науку о сложности вычислений – красивую и богатую глубокими результатами область математики. Если теория алгоритмов пытается ответить на вопрос "что можно и чего нельзя вычислить на компьютере?", то теория сложности уточняет "что можно вычислить быстро?", "что принципиально невозможно вычислить быстро?", "что делает трудные задачи трудными?", "можно ли использовать случайность, чтобы ускорить вычисления?". Чтобы (попытаться) ответить на эти вопросы, мы разобьём задачи на классы сложности и будем сравнивать разные классы между собой. Некоторые из наших теорем будут чисто теоретическими (зато очень красивыми!), а некоторые будут иметь прямые приложения в алгоритмической практике, на которые мы постараемся явно указывать.

Каждую неделю будет проходить «занятие» (одна пара) – смесь лекции и семинара в меняющейся пропорции. Будут задачи для самостоятельного решения, расширяющие и дополняющие материал занятий.

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

==Общая информация==
'''Официальное название:''' «Теория вычислений». (Никакой "и логики" в названии нет, хотя в программе она может появиться (см. курсив в программе курса)).

'''Преподаватель:''' [https://www.hse.ru/org/persons/305069360 Антон Гнатенко], почта: [mailto:agnatenko@hse.ru agnatenko@hse.ru], телеграм: [https://t.me/antongnatenko @antongnatenko]. Всюду на этой странице местоимение «я» обозначает именно этого человека.

'''Время и место (с 1 февраля):''' понедельник, 16:20, 
онлайн (по крайней мере, до возвращения оффлайн занятий, но, возможно, и после). Zoom: чтобы узнать ссылку, добавляйтесь в чат.

'''Записи занятий:''' https://www.youtube.com/playlist?list=PLbjUsKUoAqLMSKdVtO89OhR3J1alX4Q83

'''Доски:''' https://drive.google.com/drive/folders/1Qw4L9QccTVEpyG3Md_4ji1coDovKiMMy?usp=sharing

'''Телеграм-чат:''' https://t.me/joinchat/FehKYBXfk1Mu7npLZ3Tt_w

Ссылка на эту страницу: https://tinyurl.com/logicomp

Форма для задач: https://forms.gle/fvZhCKN4BmRTRRB76

Таблица с оценками: https://docs.google.com/spreadsheets/d/17KphnPJQ0AeRDcMryRnregEAJ2ZiupJN4OtK8XncAmA/edit?usp=sharing

==История==
'''1 февраля 2021. Занятие 1.''' Машины Тьюринга и класс P.

Видеозапись: https://youtu.be/_9OeqVJ0Lpw
<br>
<br>

'''5 февраля 2021. Появились тренировочные задачи по машинам Тьюринга.''' См. раздел "Задачи".
<br>
<br>

'''8 февраля 2021. Занятие 2.''' Недетерминированные машины и класс NP.

Видеозапись: https://youtu.be/HlYOfCfgQEM
<br>
<br>

'''15 февраля 2021. Занятие 3.''' Полиномиальная сводимость и NP-полнота. Теорема Кука-Левина.

Видеозапись: https://youtu.be/XokMRfTbKkQ

'''Появилась первая порция задач.''' Мягкий дедлайн - 28 марта. Вероятно, у второй порции задач дедлайн будет ''тот же''. У бонусных задач дедлайна нет. См. раздел "Задачи".
<br>
<br>

'''22 февраля 2021. Занятие 4.''' NP-полнота задач о клике, о раскраске в 3 цвета, о гамильтоновом цикле.

Видеозапись: https://youtu.be/ffv1WXM4EJ4
<br>
<br>

'''Первая порция задач пополнилась.''' Добавилось ещё немного задач на доказательство NP-полноты. Мягкий дедлайн тот же - 28 марта. См. раздел "Задачи".
<br>
<br>

'''1 марта 2021. Занятие 5.''' Полиномиальная иерархия. Иерархия по времени.

Видеозапись: https://youtu.be/FcTpfNlO4b8
<br>
<br>

'''15 марта 2021. Занятие 6.''' Вероятностные алгоритмы. Задача Polynomial Identity Testing. Виды вероятностных алгоритмов и уменьшение вероятности ошибки. Определения (неформальные) классов RP, coRP, BPP и (совсем неформально) ZPP.

Видеозапись: https://youtu.be/YCXpXFN6Ryk
<br>
<br>

'''22 марта 2021. Занятие 7.''' Классы RP, coRP, BPP, ZPP. Теорема о равенстве ZPP и RP \cap coRP. Теорема о том, что BPP \subset P/poly (не слишком формально).

Видеозапись: https://youtu.be/UVrlzOCTiTI
<br>
<br>

'''26 марта 2021. Появилась вторая порция задач.''' Мягкий дедлайн - 30 апреля. У бонусных задач дедлайна нет. См. раздел "Задачи".
<br>
<br>

'''5 апреля 2021. Занятие 8.''' Интерактивные доказательства и протоколы Артура-Мерлина. Классы IP и AM. NP \subset IP. Протокол Артура-Мерлина для задачи не-изоморфизма графов. 

Видеозапись: https://youtu.be/9k4iaxSyErU
<br>
<br>

'''12 апреля 2021. Занятие 9.''' MA \subset AM. Задача изоморфизма графов вряд ли NP-полная. IP \subset EXP.

Видеозапись: https://youtu.be/6hsOYTY7fcQ
<br>
<br>

'''Появилась третья порция задач.''' Мягкий дедлайн - 16 мая. См. раздел "Задачи".
<br>
<br>

'''19 апреля 2021. Занятие 10.''' Вероятностно проверяемые доказательства. Приближённые алгоритмы. PCP-теорема и трудность аппроксимации. Идея доказательства NP \subset PCP(poly, 1).

Видеозапись: https://youtu.be/I1WYYJKoluY
<br>
<br>

'''3 мая 2021. Появилась бонусная порция задач''' о сложности по памяти. См. раздел "Задачи".
<br>
<br>

'''24 мая 2021. Занятие 12.''' Коммуникационная сложность. Метод прямоугольников и метод ранга.

Видеозапись: https://youtu.be/eYLibOyBVsE
<br>
<br>

'''Появилась четвёртая порция задач.''' Дедлайн - конец курса. См. раздел "Задачи".
<br>
<br>

'''31 мая 2021. Занятие 13.''' Коммуникационная сложность. Покрытия и недетерминизм.

Видеозапись: https://youtu.be/5RfQGRykPyA
<br>
<br>

'''24 июня 2021. Разбор некоторых задач.''' 

Видеозапись: https://youtu.be/n_SOjIzfxyw

==Программа курса (примерная)==

Темы, написанные прямым шрифтом – обязательные, это классика теории сложности вычислений. Темы, написанные курсивом, – дополнительные. Мы рассмотрим некоторые из них, если будет на то желание слушателей. Если ''курсивные темы'' станут реальностью, они могут вытеснить обычные темы и занять их место.

* [пройдено] Временная сложность, классы P и NP. 
* [пройдено] NP-трудные и NP-полные задачи, NP-полнота задачи о выполнимости КНФ, о клике, о раскраске графа в 3 цвета, о существовании гамильтонова пути и других.
* ''Решение NP-полных задач на практике (общий обзор).''
* [пройдено] Класс coNP. ''Полиномиальная иерархия. Теорема о коллапсе полиномиальной иерархии.''
* [пройдено в виде задач] Пространственная сложность, класс PSPACE, PSPACE-полные задачи ''и попытки решать их на практике (общий обзор)''.
* ''Сложность вычислений с помощью схем из функциональных элементов, класс P/poly.''
* ''Коммуникационная сложность.''
* [пройдено] ''Вероятностная сложность, класс BPP (и другие), вероятностные алгоритмы проверки числа на простоту и проверки полиномов на равенство.''
* [пройдено] ''Интерактивные доказательства и вероятностно проверяемые доказательства.''
* ''Разрешимость и сложность некоторых логических теорий, автоматы над бесконечными словами.''
* ''Вычисления с оракулом. Арифметическая иерархия и аналитическая иерархия.''

* '''''...''''' (это многоточие написано ''курсивом'')

==Правила оценивания==
Чтобы получить оценку, нужно набирать баллы (обычные и бонусные). Вот как это сделать:

* '''Решать задачи''', которые предлагаются на занятиях и появляются на этой страничке в разделе [http://wiki.cs.hse.ru/%D0%A4%D0%B0%D0%BA%D1%83%D0%BB%D1%8C%D1%82%D0%B0%D1%82%D0%B8%D0%B2_%22%D0%A2%D0%B5%D0%BE%D1%80%D0%B8%D1%8F_%D0%B2%D1%8B%D1%87%D0%B8%D1%81%D0%BB%D0%B5%D0%BD%D0%B8%D0%B9_%D0%B8_%D0%BB%D0%BE%D0%B3%D0%B8%D0%BA%D0%B0%22#.D0.97.D0.B0.D0.B4.D0.B0.D1.87.D0.B8 «Задачи»]. Для каждой задачи указано количество баллов, которые можно получить за правильное решение. У каждой задачи есть мягкий дедлайн — после него правильные решения получат половину баллов. Задачи можно сдавать устно или письменно. В случае письменной сдачи может потребоваться дополнительное обсуждение некоторых неслучайно выбранных задач. Во время обсуждения нужно продемонстрировать понимание сданного решения. Зато можно исправить ошибки, если они там есть.

* '''Решать бонусные задачи''', которые появляются там же. За бонусные задачи даются '''бонусные баллы''' (см. ниже).

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

Пусть теперь M = «максимально возможное количество обычных баллов», а S = «сумма всех баллов (обычных и бонусных), набранных студентом за семестр».
Тогда оценка за курс вычисляется по формуле P = min{S / M * 10, 10}.

Таким образом, можно получить 10 баллов, просто решая обычные задачи. Но это проще сделать, если набирать бонусные баллы.

==Задачи==
'''Письменные решения нужно сдавать [https://forms.gle/fvZhCKN4BmRTRRB76 вот этой гугл-форме].''' Пожалуйста, оформляйте решения аккуратно. Для оцифровки записей лучше всего использовать не фото, а специальные приложения-сканеры. Например, Camscanner. Если вы сдаёте несколько задач сразу, объединяйте их в один пдф или в один архив.

Для сдачи файлов в форму нужен гугл-аккаунт. Если его нет и по каким-то причинам вы совсем не хотите его заводить, можно сдавать задачи устно или договориться о каком-либо ещё варианте. Но лучше всё-таки завести аккаунт.

'''Правила оформления решений.''' При изложении решений рекомендуется соблюдать разумный баланс между строгостью и размахиванием руками. Если требуется доказать, например, принадлежность некоторого языка классу NP, то достаточно предоставить словесное описание соответствующей машины (если только в условии явно не просят построить машину). Описание должно быть, тем не менее, чётким и подробным (но без фанатизма). Если какие-то важные детали из этого описания будут неясны, я попрошу сделать пояснения (возможно, устные). 

'''Можно сдавать задачи устно.''' Для этого нужно связаться со мной в зуме, включить демонстрацию экрана (либо ещё каким-то образом добиться того, чтобы я видел какие-то записи и понимал, о чём вы говорите) и рассказать своё решение, отвечая на возникающие вопросы. Нужно предупредить меня о желании сдавать хотя бы за день (например, написав в телеграм), и мы договоримся о времени. Можно предупреждать раньше, чем за день – это приветствуется. Можно попробовать договориться прямо в день сдачи, но успех в таком случае маловероятен.


====Наборы задач====

* [https://drive.google.com/file/d/1jwjO29czncdbgozvNjdn0ZFjXsZo_e28/view?usp=sharing Тренировочные задачи по машинам Тьюринга]. Дедлайна нет.
* [https://drive.google.com/file/d/16Ae7UVOWY2-HhH8yG3DS8eBwJstz7O7D/view?usp=sharing Первая порция задач: класс NP, полиномиальная сводимость и NP-полнота]. Мягкий дедлайн 28 марта. По бонусным задачам дедлайна нет.
* [https://drive.google.com/file/d/1A5HEZwE4Ezga4Z6DuT3SLw0eHp2h17PB/view?usp=sharing Вторая порция задач: вероятностные вычисления]. Мягкий дедлайн 30 апреля. По бонусным задачам дедлайна нет.
* [https://drive.google.com/file/d/1vXz32rLU_T35MKfslndJ0bgF9P-yHQ38/view?usp=sharing Третья порция задач: интерактивные доказательства]. Мягкий дедлайн 16 мая. Обратите внимание, что в обычных задачах теперь могут быть бонусные баллы. Они так же, как и обычные, наполовину уменьшатся после дедлайна. Подробнее читайте в листочке. После 19 апреля в этом листочке может появиться ещё пара задач с тем же дедлайном.

* [https://drive.google.com/file/d/1XRa0Wj_s-TKe8l5624fxDIZc4LdK0WCy/view?usp=sharing Бонусная порция задач: сложность по памяти]. Все задачи в этой порции — бонусные. Несколько относительно простых задач позволят набрать баллов побольше. Есть и несколько трудных задач. Все определения и теоремы, нужные для понимания и решения, приводятся в листочке.

* [https://drive.google.com/file/d/1Gx7b7ahd36j2gIkYrOWZ39o__djINtG7/view?usp=sharing Четвёртая порция задач: коммуникационная сложность]. Дедлайн: конец курса.

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

Некоторые статьи недоступны обычным пользователям. Но к ним можно получить доступ через библиотеку Вышки: https://library.hse.ru/e-resources (см. "Базы данных зарубежной периодики" и там "издания ACM"; у вас должны быть логин/пароль для библиотеки: https://elib.hse.ru/e-resources/ez/ezregulation.htm).

=== Классика ===

* J. Hartmanis & R. E. Stearns. [http://www.cs.albany.edu/~res/comp_complexity_ams_1965.pdf On the complexity of algorithms] (1965). (Статья, с которой началась теория сложности вычислений).

* Stephen A. Cook. [https://dl.acm.org/doi/10.1145/800157.805047 The complexity of theorem-proving procedures] (1971). (Определение полноты (осторожно: не совсем такое, как у нас)  и теорема Кука-Левина).

* Richard M. Karp. [https://people.eecs.berkeley.edu/~luca/cs172/karp.pdf Reducibility among combinatorial problems] (1972). (Внушительный список комбинаторных задач с доказательствами их NP-полноты).

* Л. А. Левин. [http://www.mathnet.ru/links/efc20ed39c74803d8ecb1011962ba4b3/ppi914.pdf Универсальные задачи перебора] (1973). (Примерно про то же in Soviet Russia)

=== Неоклассика ===
* M. Agrawal, N. Kayal & N. Saxena. [https://annals.math.princeton.edu/wp-content/uploads/annals-v160-n2-p12.pdf PRIMES is in P] (2004). (Полиномиальный алгоритм проверки числа на простоту)

* Alexander A. Razborov & Steven Rudich. [https://reader.elsevier.com/reader/sd/pii/S002200009791494X?token=FA3F4242B7E505CE6CB80008B59A32F704FAF5C15051D9694B44548A3AFFF4F47B4E03BAFC6B8357EC27E4FCE360652C Natural Proofs]

* S. Goldwasser & M. Sipser. [https://dl.acm.org/doi/abs/10.1145/12130.12137 Private Coins versus Public Coins in Interactive Proof Systems] (Открытые случайные биты (почти) не хуже, чем закрытые)

* O. Goldreich et al. [http://www.wisdom.weizmann.ac.il/~oded/PSX/fgmsz.pdf On Completeness and Soundness in Interactive Proof Systems] (Распознавание x \in L с вероятностью 1 для систем интерактивных доказательств)

==Литература==
# Dexter C. Kozen. Theory of Computation. (Замечательная книга по теории сложности вычислений, малоизвестная, по непонятным причинам, в нашей стране. Изложение структурировано в виде "лекций", часть из которых "обычные", а часть "продвинутые")
# Michael Sipser. Introduction to the Theory of Computation (Очень хороший вводный учебник)
# Sanjeev Arora & Boaz Barak. Computational Complexity: A Modern Approach. (Большая книга, которая входит во все списки литературы по теории сложности вычислений)

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

# Д.В. Мусатов. Лекции по сложности вычислений в МФТИ: [https://mipt.lectoriy.ru/course/Maths-ComputationalComplexity-14L видеолекции].
# Jonathan Katz. Курс в университете Мэриленда: [https://www.cs.umd.edu/~jkatz/complexity/f11/ страница курса (есть конспекты)].
# Rafael Pass. Курс в Корнеллском университете: [http://www.cs.cornell.edu/courses/cs6810/2009sp/ страница курса (есть конспекты)].

==Архив==
* [http://wiki.cs.hse.ru/%D0%A4%D0%B0%D0%BA%D1%83%D0%BB%D1%8C%D1%82%D0%B0%D1%82%D0%B8%D0%B2_%22%D0%A2%D0%B5%D0%BE%D1%80%D0%B8%D1%8F_%D0%B2%D1%8B%D1%87%D0%B8%D1%81%D0%BB%D0%B5%D0%BD%D0%B8%D0%B9_%D0%B8_%D0%BB%D0%BE%D0%B3%D0%B8%D0%BA%D0%B0%22_(%D0%9E%D1%81%D0%B5%D0%BD%D1%8C_2020) Факультатив "Вычислимость и логика", осень 2020]