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

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

#дневниклекций На прошедших двух лекциях 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/1QgJq-U5aDJjDnsLLBxRB8mtxIW2XYUa_pVzk_0Hd4QA/edit?usp=sharing Домашка формально разбита на 2 файла, но скорее всего будет выдана одновременно. Проект можно сделать по желанию, он оценивается как 3 задачи из домашки, темы тоже выложу вместе с домашкой. По дате контрольной чуть позже сделаю опрос. Будет 2 даты на выбор: в мае и июне.

В итоге осенью будет спецкурс про PCP (вероятностно проверяемые доказательства) - у него и формальное большинство в голосовании. Кто хочет ходить или хотя бы получать информацию, приходите в чат https://t.me/+DMJlW-9mXIMzZjky

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