Сложность вычислений ФПМИ

#дневниклекций
Попробую в этом семестре записывать, что прошли на лекциях. Если что-то важное забываю, дополняйте. В прошлый раз была начальная лекция про интерактивные доказательства. Примерное содержание:
- Доказательство как текст и как процесс. Пример с разноцветными носками.
- Общее определение интерактивной системы доказательств с прувером и верификатором. Класс IP. Тривиальные вложения NP и BPP в IP, протокол для задачи GNI (о неизоморфизме графов).
- Независимость класса от точных порогов ошибки (через амплификацию). Варианты с совпадением порогов для строгих неравенств и с идеальной полнотой должны были разбираться на семинаре.
- Вложение IP в PSPACE через вычисление оптимальных ответов прувера на полиномиальной памяти. (Доказали для упрощённого случая).
- Вариант с общими случайными битами. Классы MA и AM. Вложение МА в АМ. Утверждения про многраундовый АМ (с константным числом раундов - так же, как с двумя, с полиномиальным - как IP, пока без доказательств)

Сложность вычислений ФПМИ pinned «Служебный пост с информацией на весну 2026 для курсов «Сложность вычислений: дополнительные главы» в бакалавриате ДМ и «Дополнительные главы теории сложности» в магистратуре (будет дополняться). Расписание: Лекции - Даниил Мусатов, четверг, 10:45, 424 Арктика…»

Служебный пост с информацией на весну 2026 для курсов «Сложность вычислений: дополнительные главы» в бакалавриате ДМ и «Дополнительные главы теории сложности» в магистратуре (будет дополняться).

Расписание:
Лекции - Даниил Мусатов, четверг, 10:45, 424 Арктика

Семинары - Иван Смирнов, четверг, 12:20, 424 Арктика

Ссылки:
Этот канал (с новостями и материалами): https://t.me/diht_complexity
Чат для обсуждений и вопросов: https://t.me/+WYa2jWEwL-VkNWUy
Папка с материалами: https://www.dropbox.com/scl/fo/9wslv92i9vqbg1cdvqr54/AGAfcvXxt7B1wdrqryhB_uE?rlkey=775k6hbqsg4k0nv9fluf6fwqt&dl=0
Табличка для оценок: https://docs.google.com/spreadsheets/d/16YrAMmJgOBkFG19q5RLJr0SQz7AdTH6h7KZ4SGt7fwU/edit?usp=sharing

Традиционно весной этот канал используется для курса дополнительных глав сложности вычислений. Если вы ходите на курс обычной сложности для ПМИ.Инф или по выбору, то подписывайтесь на канал https://t.me/compl_pmi_inf

Первая пересдача по осеннему курсу сложности будет в эту пятницу, 13 февраля, с 10 до 14 часов, аудитория 204а ГК. Пишите в личку @musatych, придёте ли вы, чтобы мы планировали число принимающих и время захода. Ещё одна пересдача точно будет на первой неделе марта, до этого - не факт.

В табличке (https://docs.google.com/spreadsheets/d/1VCDVi-esvUPujBcBZ6QeZ5UHPJpMvu7jjBYn1TYINlY/edit?usp=sharing) в основной вкладке появилось расписание захода на завтрашний экзамен (Поточная аудитория в Цифре). Можно свободно меняться временем захода (с кем-то, кто реально придёт), о результативных обменах пишите в личку, но не используйте чат курса для поиска, с кем поменяться. Если есть какие-то уважительные причины переноса времени, тоже пишите. Расписание на послезавтра появится завтра.

Как выясняется, не все внимательно прочли пункт 4.5 из программы курса ("Политика по поводу плагиата и сгенерированного текста"). Если какие-то из ваших работ сданы с его нарушением, то ещё не поздно их отозвать или отредактировать/дополнить, чтобы выполнились требования пункта.

3-я к/р прошла, подготовлена дорешка. Нужно получить оценку до получения билета на экзамене, точные сроки уточняйте у своего семинариста.
Upd: 17:20 файл изменён, скачайте заново

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

Подготовлена дорешка по второй к/р. Третью сделаю завтра, как проведём очную часть. Она будет в 12:30 в 521 ГК, ещё можно присоединиться. По программе экзамена можно ориентироваться на прошлогоднюю, сейчас я её вычитаю и вывешу новую версию. Правила перевода оценок за семестр в итоговые баллы тоже не позднее завтрашнего дня опубликую.

Несколько людей попросили сделать к/р в пятницу, и я сегодня тоже уже не успеваю её провести. Давайте предварительно считать, что к/р в пятницу в то же время 12:30 - если не подходит, сообщите. На вкладке можно переголосовать, давайте зафиксируем итог завтра вечером (в 22:00).

Также я сделал лист про дату экзамена, в той же таблице: https://docs.google.com/spreadsheets/d/1VCDVi-esvUPujBcBZ6QeZ5UHPJpMvu7jjBYn1TYINlY/edit?usp=sharing
Пока что там поставлены даты из общего расписания той группы, с которой вы ходите. Если нужно перенести, отметьте там с комментарием. Перенос по неуважительной причине не гарантируется. Если вы из магистратуры, то можете выбрать любую из двух дат.

Вторая к/р почти проверена, по ней будет дорешка со сдачей до экзамена минус 2 дня. По третьей к/р предлагается выбор: написать завтра, 17 декабря, в 12:20 по 12 баллов за задачу или дома по 8 баллов за задачу. Темы к/р: схемные классы, NC-иерархия, вероятностные классы, дерандомизация (всего 4 задачи). Выбор можно сделать на специальном листе в таблице: https://docs.google.com/spreadsheets/d/1VCDVi-esvUPujBcBZ6QeZ5UHPJpMvu7jjBYn1TYINlY/edit?usp=sharing Если хотите написать очно, но завтра не подходит, тоже отметьте, можно попробовать сделать в четверг или пятницу. Если никакого выбора не делаете, то задачи будут в домашке по 5 баллов.

Рассадка на контрольную 15:30, 110 КПМ

Рассадка на сегодня, 12:20, 113 ГК. Если пропускаете по уважительной причине, пишите в личку @musatych до начала контрольной.

В среду, 3 декабря, будет вторая контрольная. Это тренировочный вариант с задачами. Время то же, что и у первой к/р: у части групп вместо лекции, у другой части в 15:30. Табличка в файле. Если нужно перенести на другое время или вы пропускаете по уважительной причине, пишите в личку @musatych с указанием причины.

Дорешка по первой контрольной. В файле индивидуальные варианты, есть задачи, которые вы решили меньше, чем на 8 баллов, а также 2 новые задачи. Даётся 5 баллов за решение, в сумме с набранным на к/р не больше 8. За новые задачи 10 баллов. Сдача письменно семинаристу (или устно по договорённости). Срок на решение - 2 недели, до 26 ноября.

⚪️ Задача о равенстве классов P и NP в 2000 году была включена в список из 7 задач тысячелетия, за решение которых объявлена премия в миллион долларов.
⚪️ Формулируется она так: "Есть ли универсальный способ сокращения экспоненциального перебора возможных решений до какого-то полиномиального алгоритма?" Звучит страшно? Значит тебе к нам! Приходите на лекцию и вы узнаете:

-В чем же суть этой проблемы? И почему она важна для науки и всего общества?
-Историю изучения проблемы и обнаруженные препятствия к её решению.
-Почему мы верим, что P не равно NP, но не можем этого доказать? Оказывается, целые техники доказательств заведомо не могут дать результата! Хотя считается, что установлено «экспериментальное» доказательство проблемы, но математического нет даже близко!

⚫️ Даниил Мусатов - кандидат физико-математических наук, доцент кафедры дискретной математики МФТИ (г.Москва)

🗓 22 ноября 15:00
📍 Казань, ИТ-парк, ул.Петербургская, 52
🎫 Необходима регистрация
🛸 Научный лекторий Milmax Science

#milmax

Если у вас есть знакомые в Казани, можете позвать их на мою научно-популярную лекцию!

Новости про отчётность по курсу:
- Первая к/р проверена, в ближайшие дни сделаю дорешку
- Вчера был крайний срок выбора проектов. В связи с этим:
* Если забыли выбрать, срочно выберите, я пока ещё не закрыл редактирование
* Есть несколько нарушенных ограничений на число одинаковых проектов: 69 в группе 321 выбран дважды, 33 и 90 на курсе - трижды. В каждой коллизии нужно либо кому-то уйти на другую тему, либо всем прописать разные подтемы. Договоритесь, пожалуйста, друг с другом.