Информация для пересдающих завтра осенний курс. Аудитория 520 ГК, начало в 10:00, рекомендуемое время захода есть в табличке. Если время не подходит или не отмечено, пишите в личку.

Подготовлена табличка для оценок этого года: https://docs.google.com/spreadsheets/d/1wBpGmPHv2-uyMeayswf-2Dp_5I9Iy5wlnnowFKTtbFg/edit?usp=sharing . Если вас нет в табличке, напишите в личку @musatych

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

Вчера был выложен неправильный файл - с программой, а не проектами, а все тактично промолчали. Надеюсь, кто-нибудь всё же захочет сделать проект, выбирайте по этому файлу.

Сейчас начинается составление плана по спецкурсам на осенний семестр. Традиционно я читаю спецкурс на одну из продвинутых тем курса сложности вычислений. Раньше было только осенью, но последние 3 года по просьбам слушателей продолжаю и весной. В связи с тем, что студенты ПМИ.Инф уже проходили курс криптографии, а он обязательный для кафедры ДМ, он будет заменён на более продвинутый курс криптографии, так что один курс точно будет. Не уверен, что смогу совмещать с другим курсом, но при наличии интереса постараюсь. Вот несколько возможных тем, в комментариях будут примерные программы, а также неанонимный консультативный опрос (т.е. будет выбран не обязательно вариант, набравший большинство голосов).
Дополнительные главы криптографии - обязательный для ПМИ.Инф+ДМ, факультативный для всех. Рекомендуется проходить после основного курса, но в принципе можно и параллельно. Программы пока нет, но вот примерные темы: конфиденциальные дву- и многосторонние вычисления, разделение секрета, византийское соглашение, электронные выборы, электронная наличность, блокчейн, неинтерактивные доказательства с нулевым разглашением, снарки и старки, обфускация. Возможны вариации.
Вероятностно проверяемые доказательства - это то, что мы недавно проходили, так что подробное представление, думаю, не нужно. В этом курсе доказывается "большая" PCP-теорема и её вариации вроде трёхбитной теоремы Хостада, а также изучаются сложности приближённого решения разных конкретных задач. Этот курс читался в этом году, так что будет повторён только при высоком интересе.
Псевдослучайность и дерандомизация - в этом курсе изучаются разные псевдослучайные конструкции (экспандеры, экстракторы, коды с декодированием списком, генераторы псевдослучайных чисел и др.), которые в конечном итоге могут привести к доказательству BPP=P. Этот курс читался в прошлом году, но при высоком интересе повторю.
Вычислительная сложность задач поиска - изучается сложность задач поиска, прежде всего тех, где ответ точно есть (и потому вопрос о существовании ответа тривиален). Есть растущий зоопарк классов, а также много приложений к разного рода экономическим моделям на базе теорем о неподвижных точках.
Рациональные интерактивные доказательства - изучается делегирование вычислений, при котором мощный сервер выполняет вычисления за деньги, максимизируя вознаграждение. Нужно так выстроить стимулы, чтобы при этом сервер выявил правильный ответ. Кратко будем изучать эту тему завтра.

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

Готова вторая домашняя работа. К сожалению, на выполнение мы можем дать время только до следующей субботы, потом учебный офис начнёт активно просить оценки, а нам ещё нужно будет проверить. Гарантированные пороги на оценки внутри файла.

Контрольная работа состоится в четверг, 22 мая, с 10:45 до 13:45. Вероятно, в 432 ГК, но я ещё уточню на всякий случай. Это вариант прошлого года, выкладываю в качестве тренировочного.
Для магистров: у вас это экзамен, так что времени больше. Зарезервирована дата 10 июня, если хотите написать в неё, пишите в личку. Кто из магистров хотел перезачесть оценку из бакалавриата, также напишите ещё раз.

Небольшое изменение: контрольная сегодня будет в 430 ГК. Приходите к 10:45.

Завтра будет контрольная для тех, кто сдаёт курс в магистратуре. Приходите в 10:00 в 115 КПМ.

Поздравляю всех с днём знаний и начало учебного года! Тех, кто продолжает изучение сложностной линейки на курсе криптографии, приглашаю подписаться на канал https://t.me/fpmi_crypto, там уже есть верхний служебный пост с основной информацией по курсу.

Служебный пост с информацией на осень 2025 (будет дополняться).

Расписание:
Лекции - Даниил Мусатов, среда, 12:20, 113 ГК

Семинары:
320 (Классика-основа) - Игорь Шиманогов, ср, 10:45, 520 ГК
321 (Классика-основа) - Максим Коротков, ср, 13:55, 516а ГК
322+323 (Классика-основа) - Константин Ковалёв, пт, 13:55, 521 ГК
324 (Математика) - Илья Степанов, вт, 15:30, 2.35 Цифра
327 (Классика-основа+продва) - Фёдор Киселёв, вт, 12:20, 526 ГК
328 (Классика-продва) - Виталий Пырэу, чт, 9:00, 516а ГК
512 (Магистратура блокчейн) - Сергей Васильчишин, вт, 17:05, онлайн

Этот канал (с новостями и материалами): https://t.me/diht_complexity
Чат для обсуждений и вопросов: https://t.me/+WYa2jWEwL-VkNWUy
Папка с материалами: https://www.dropbox.com/scl/fo/hkp9wjr1os4klspstglp2/ADx6R-lEmdrQeuupGpqK5AY?rlkey=oh4bgn7wkn5qocwghr3s7vssn&st=trfc44g5&dl=0
Табличка для оценок: https://docs.google.com/spreadsheets/d/1VCDVi-esvUPujBcBZ6QeZ5UHPJpMvu7jjBYn1TYINlY/edit?usp=sharing

Сегодня первая лекция в 12:20 в 113 ГК. Она будет вводная: сначала немного расскажу про курс и формальности, потом будет научно-популярный рассказ про проблему P=?NP. Приходите!

По этому курсу (и некоторым его продолжениям) у меня есть книга. Я её пишу уже много лет, но пока что она всё ещё в статусе черновика: часть глав и разделов пропущена, местами остаются следы перестановок кусков текста и даже есть заметки todo. Тем не менее, она вполне годится для изучения материала и подготовки к экзамену. Выкладываю последнюю версию на текущий момент, в течение семестра возможны обновления.

#дневниклекций
Буду стараться писать сюда, что успели пройти на лекциях. Если пропускаю что-то важное, дополняйте. Сегодня было:
- Рассказ о курсе и системе оценивания.
- Неформальное определение P и NP, переборное решение задач из NP
- Примеры похожих друг на друга задач, имеющих разную сложность: раскраска в 2 и 3 цвета, эйлеровость и гамильтоновость, проверки на простоту и на наличие простого делителя в данном диапазоне
- Обсуждение, почему полиномиальность и эффективность это синонимы
- Роль вопроса о P и NP в машинном доказательстве теорем
- 5 миров Импальяццо: возможные статусы решения проблемы и их последствия для общества, в том числе связь с криптографией
- Обнаруженные барьеры к решению проблемы P/NP.

В следующий раз будем изучать временны̀е сложностные классы - детерминированные, недетерминированные и ко-классы.

Объявление о спецкурсе (для уже прошедших курс сложности).

В этом семестре я читаю спецкурс "Рациональные интерактивные доказательства". В нём подробно рассматривается новый раздел на стыке теории сложности вычислений и теории игр – рациональные интерактивные доказательства. Они могут служить для моделирования коммерческих вычислений, когда у заказчика вычислений нет способа проверить истинность результата, но он может выстроить стимулы так, чтобы исполнителю было выгодно выполнить вычисления правильно. Курс будет заточен на теоретические аспекты: мы определим несколько сложностных классов, основанных на этой идее, и докажем соотношения между ними и классическими классами. В частности, выяснится, что за константное число раундов можно решить гораздо больше задач, чем в классических интерактивных доказательствах.

Курс проходит по четвергам в 15:30, 535 ГК. Первое занятие - 11 сентября. Чат курса - https://t.me/+V8LdajB3dUjKbhjM

#дневниклекций
Сегодня изучали разные сложностные классы, связанные с затраченным временем:
- Измерение времени работы машины, решающей данную задачу
- Асимптотики o, O, Θ, Ω, ω
- Классы DTIME(T(n))
- Временные сложностные классы P, QP, SUBEXP, E, EXP, EEXP и т.д. Теорема об иерархии по времени (б/д, применительно к указанным классам)
- Примеры задач из класса P: разные конкретные примеры и неконструктивные доказательства через миноры графов и теорему Робертсона-Сеймура
- Примеры задач из класса QP: перебор нужного размера и доминирующие множества в турнирах
- Примеры задач из E и EXP: перебор и поиск выигрышных стратегий
- Недетерминированные машины Тьюринга
- Два определения класса NP: через верификаторы и через НМТ. Их эквивалентность. Другие классы NTIME(T(n)), NEXP
- Класс coNP и примеры задач из пересечения NP и coNP: FACTORING и игры специального вида

#дневниклекций
Вчера была первая лекция про NP-полноту - центральную тему первой части курса. Изучили следующее:
- Полиномиальная сводимость (по Карпу) и её основные свойства
- Определение NP-трудности и NP-полноты. Получение новых NP-трудных и NP-полных задач через сводимость
- Общая картина NP-полных, NP-трудных и NP-промежуточных задач. Теорема Ладнера (б/д)
- Генерическая NP-полная задача и доказательство, что она действительно NP-полная
- Задачи SAT и 3SAT, а также CSP и qCSP. Сводимости 3COL к 4CSP и SAT к 3SAT
- Теорема Кука-Левина: формулировка, построение таблицы по одноленточной машине Тьюринга, построение формул, выражающих корректность начальной конфигурации, итоговое принимающее состояние и корректность всех переходов (последняя - через идею локальности вычислений). Итоговая компоновка доказательства теоремы из этих компонентов.

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