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

#дневниклекций В прошлый раз обсуждали подробно про АМ-классы: - Напоминание определений: классы МА, АМ, более высокие вроде АМА и МАМ и общий AM[k] - Формулировка теоремы об ускорении: AM[const]=AM, AM[2k(n)]=AM[k(n)] - Схема доказательства первой части: амплификация, вложения типа AMA=AAM=AM. - Вложение АМ и МА в полиномиальную иерархию. - Формулировка теоремы Голдвассер-Сипсера о моделировании частных битов при помощи общих. Идея доказательства на примере задачи о неизоморфизме: сведение к оценке размера некоторого множества, принадлежность к которому Мерлин может удостоверять. Обсуждение, почему не работает обычный метод Монте-Карло. - Почему, исходя из всего предыдущего, в конце 80-х учёные думали, что IP это не очень большой класс Завтра будем разбираться, какой метод работает, и начнём разбирать IP=PSPACE

Объявление: завтра семинара не будет, только лекция. Вероятно, 19 марта не будет лекции, а будет 2 семинара.

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

Служебный пост с информацией на весну 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 из программы курса ("Политика по поводу плагиата и сгенерированного текста"). Если какие-то из ваших работ сданы с его нарушением, то ещё не поздно их отозвать или отредактировать/дополнить, чтобы выполнились требования пункта.

Несколько людей попросили сделать к/р в пятницу, и я сегодня тоже уже не успеваю её провести. Давайте предварительно считать, что к/р в пятницу в то же время 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 баллов.

⚪️ Задача о равенстве классов P и NP в 2000 году была включена в список из 7 задач тысячелетия, за решение которых объявлена премия в миллион долларов. ⚪️ Формулируется она так: "Есть ли универсальный способ сокращения экспоненциального перебора возможных решений до какого-то полиномиального алгоритма?" Звучит страшно? Значит тебе к нам! Приходите на лекцию и вы узнаете: -В чем же суть этой проблемы? И почему она важна для науки и всего общества? -Историю изучения проблемы и обнаруженные препятствия к её решению. -Почему мы верим, что P не равно NP, но не можем этого доказать? Оказывается, целые техники доказательств заведомо не могут дать результата! Хотя считается, что установлено «экспериментальное» доказательство проблемы, но математического нет даже близко! ⚫️ Даниил Мусатов - кандидат физико-математических наук, доцент кафедры дискретной математики МФТИ (г.Москва) 🗓 22 ноября 15:00 📍 Казань, ИТ-парк, ул.Петербургская, 52 🎫 Необходима регистрация 🛸 Научный лекторий Milmax Science #milmax

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