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

#дневниклекций
На прошедших двух лекциях 8 и 22 октября изучали полиномиальную иерархию и начали полиномиальную память. Немного подробнее про то, что было:
- Задача о проверке значения кликового числа. Почему она NP-трудна, но скорее всего не в NP. Представление её как разности двух языков из NP. Преобразование в формулу с двумя кванторами. Класс DP.
- Другие примеры возникновения формулы с двумя или тремя кванторами: минимизация формулы, кликовая раскраска, в том числе наследственная, обобщённая рамсеевость, размерность Вапника-Червоненкиса
- Определение классов полиномиальной иерархии, вложения одних в другие.
- Если P=NP, то P=PH.
- Три условия коллапсирования полиномиальной иерархии, их эквивалентность.
- Существование полных задач на уровнях иерархии. Задачи Sigma_k-SAT и Pi_k-SAT, эквивалентность друг другу их полноты в соответствующих классах для каждого k. Доказательство полноты для случая, когда последний квантор - квантор существования. Эквивалентность существования полной задачи во всей иерархии и её коллапсирования.
- Альтернирующие машины и их связь с полиномиальной иерархией.
- Игровой взгляд на задачи из PH как множества выигрышных позиций в играх с фиксированным числом ходов.
- Измерение памяти, используемой машиной. Модель с неизменяемым входом и рабочей лентой. Классы DSPACE(s(n)) и NSPACE(s(n)).
- Соотношения временных и пространственных классов: L вложено в P, PSPACE вложено в EXP, NL вложено в P (доказательство через конфигурационный граф). Формулировка теоремы Сэвича, следствие: PSPACE=NPSPACE.

Сегодня докажем теорему Сэвича и поговорим о PSPACE-полных задачах. Если останется время, посмотрим на задачи из класса L.

Публикуем обновлённый файл со списком проектов и открываем запись на них. Подробные правила описаны в файле, но основное правило выбора темы - не заявляться более чем вдвоём на одну тему, а если всё же заявились, то вписывать уточнение, почему получаются разные подтемы. Это будет проверяться. Запись открыта в табличке: https://docs.google.com/spreadsheets/d/1VCDVi-esvUPujBcBZ6QeZ5UHPJpMvu7jjBYn1TYINlY/edit?usp=sharing на листе Проекты, столбцы D и E должны редактироваться. В строках 143-258 проверяется число записавшихся, там же можно искать свободные темы.

Если вас интересует, почему так много сообщений в чате, то обсуждается очередная странная попытка доказать, что P не равно NP. Если есть дела важнее, можно смело всё пролистать.

А это рассадка на вторую часть к/р, в 15:30, 110 КПМ. Приходите! Upd. В рассадке была ошибка, файл заменён в 14:13.

Рассадка на первую часть к/р, в 12:20. Приходите!

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

Как я вчера сказал на лекции, через неделю, 15 октября, будет контрольная. В этом файле написано, в каких группах какие задачи будут и в какое время к/р (у части групп во время лекции, у части на 5-й паре). Чуть позже сделают табличку, можно будет поменять время при необходимости.

#дневниклекций
Сегодня были 3 слабо связанные между собой темы: задачи подсчёта, задачи аппроксимации и пэддинг. Изучили следующее:
- Постановка задачи подсчёта: по входу x нужно найти число таких y, что V(x,y)=1. Класс #P для полиномиальных V. Понятие NP-трудности для задач подсчёта. Сводимость по Куку.
- (Очевидная) NP-трудность задачи подсчёта, соответствующей NP-полной задаче распознавания. Пример, когда задача распознавания полиномиальна, а задача подсчёта NP-трудна: число простых циклов в ориентированном графе. Построение сводимости: гаджет-"конфета", замена рёбер на него, подсчёт числа циклов в двух случаях, итоговая конструкция сводимости.
- Пара слов про задачу о перманенте.
- Постановка задач оптимизации и аппроксимации. Два варианта в каждом случае: поиск оптимума и точки оптимума. Пример, когда задача точной оптимизации NP-трудна, а аппроксимации - полиномиальна (Задача о вершинном покрытии). Вариации задачи коммивояжёра: общая (NP-трудная для любой точности), метрическая (полиномиально разрешимая с множителем 3/2, алгоритм Кристофидеса-Сердюкова), евклидова (полиномиально разрешимая с любой точностью, алгоритм Ароры).
- Классы задач оптимизации и аппроксимации: NPO, APX, PTAS, FPTAS.
- Понятие об NP-трудности задач аппроксимации. Формулировка теоремы для задачи MAX3SAT: существование приближённого алгоритма с множителем 7/8 и NP-трудность аппроксимации с множителем 7/8+ε (PCP-теорема).
- Метод пэддинга (изменения масштаба задачи). Общая идея и два приложения: если P=NP, то EXP=NEXP, а также NP≠E (вывод из E≠EXP).

#дневниклекций
Сегодня была вторая лекция про NP-полноту. Обсуждали несколько конкретных задач, а также задачи поиска. Изучили вот что:
- Задачи, связанные с гамильтоновыми путями: HAMPATH (существует ли гамильтонов путь в орграфе из s в t), HAMCYCLE (существует ли гамильтонов цикл в орграфе), аналоги для неориентированных графов, задача коммивояжёра.
- Сведение HAMPATH к HAMCYCLE: неправильность очевидной конструкции и её исправление.
- Сведение 3SAT к HAMCYCLE: гаджеты-ромбы, гирлянда и вершины для скобок, обоснование корректности сведения
- Сведение HAMPATH к UHAMPATH: недостаточность снятие ориентации, конструкция с утроением вершин
- Сведение UHAMCYCLE к TSP
- Задача NAE-SAT о существовании набора, при котором в каждой скобке есть истинные и ложные литералы. Сведение 3SAT к NAE-SAT
- Сведение NAE-SAT к 3COL
- Задачи поиска: определение, сводимость по Левину
- Сводимость задач поиска к задачам распознавания на примере задачи о клике. Рекурсивная конструкция через самосводимость
- Кратко о задачах подсчёта и аппроксимации (подробнее в следующий раз)

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

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

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

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

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

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

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

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

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

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

Сложность вычислений ФПМИ pinned «Служебный пост с информацией на осень 2025 (будет дополняться). Расписание: Лекции - Даниил Мусатов, среда, 12:20, 113 ГК Семинары: 320 (Классика-основа) - Игорь Шиманогов, ср, 10:45, 520 ГК 321 (Классика-основа) - Максим Коротков, ср, 13:55, 516а ГК 322+323…»

Служебный пост с информацией на осень 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

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

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