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

https://drive.google.com/file/d/1Igi8sjB_vSHReLGTt2s0Y6iN3CQ0MNhs/view?usp=sharing - запись сегодняшней лекции

Содержимое доски сегодня

Напоминаю, что сегодня будет лекция про проблему "P=NP?" Начало в 13:55 по ссылке https://meet.google.com/ina-nwod-way Если будете слушать не с аккаунта phystech.edu, пожалуйста, не опаздывайте, подключайтесь с 13:50.

Институт математики им. Стеклова и МФТИ открывают базовую кафедру, в рамках которой будет читаться линейка алгоритмических курсов. Вот список курсов и расписание:
пн 10:00 — 11:25: «Теория чисел» (лектор М.Р. Габдуллин)
пн 11:30 — 12:55: «Доказуемость и формальная арифметика» (лекторы Л.Д. Беклемишев и Т.Л. Яворская)
вт 13:35 — 15:00: «Сложность вычислений» (лектор В.В. Подольский, курс общий с «квантовой» линейкой)
вт 15:00 — 16:25: «Геометрическая теория групп» (лектор И.Г. Лысёнок)
вт 17:45 — 19:15: «Сходимость случайных процессов» (лектор В.И. Афанасьев)
Курсы планируются онлайн, некоторые могут быть офлайн в здании МИАН (м. Академическая). Курсы Беклемишева/Яворской и Подольского точно должны быть очень интересными. Подробности можно узнать у куратора программы Степана Кузнецова по адресу sk(собака)mi-ras.ru. О возможностях перезачёта в физтехе можно договориться в индивидуальном порядке. Про зачёт курса Подольского вместо какой-то части моего будет централизованное решение в течение недели.

Завтра у большинства групп первый семинар, прикладываю .pdf

Объявление для 4-курсников, которые будут ходить на курс криптографии. Присоединяйтесь к чату, будем там курс обсуждать: https://t.me/joinchat/DZlFTQ8qiK7Ymz7GXLiaKw (Как водится, там есть прошлогодняя история)

https://drive.google.com/file/d/17aUF62lNlUFF3DQAWgOVnboquV278NNs/view?usp=sharing - запись сегодняшней лекции. Почему-то там ещё лишний час в конце записался.

Это содержимое доски сегодняшней лекции. Запись должен автоматически обработать Гугл-Мит, но пока не обработал. Надеюсь, всё закончится успешно и я её опубликую.

Это текущая версия моей книги по сложности вычислений. Возможно, в ходе семестра текст будет обновляться, тогда буду выкладывать новые версии.

Поздравляю с началом нового учебного года! Рад приветствовать третьекурсников на курсе по сложности вычислений. Тех, кто уже прошёл курс, приглашаю при желании оставаться в чате и помогать младшим товарищам. Лекции будут проходить на платформе Гугл-Мит по ссылке https://meet.google.com/ina-nwod-way. Распространите среди тех, кто не подписан на этот канал, а лучше подпишите их. Ссылка постоянная. Запись будет. Первая лекция сегодня в 13:55.

В итоге осенью будет спецкурс про рациональные доказательства. Кто заинтересован его слушать, присоединяйтесь к чату https://t.me/joinchat/DZlFTVfC3Wo-3aq4ym4YzA Программы пока нет, но к началу курса постараюсь сделать. Хотя что-то и по ходу можно будет варьировать.

В опросе про спецкурс пока что с отрывом лидируют рациональные доказательства. Новых голосов долго не поступало. Так что предлагаю утвердить. А про другие темы ещё успею прочесть в другие годы.

Проверка окончена. Определены пороги на оценки:
125 - 10 баллов
114 - 9 баллов
100 - 8 баллов
90 - 7 баллов
80 - 6 баллов
70 - 5 баллов
59 - 4 балла
47 - 3 балла
Поскольку с меня оценки уже срочно просят, я их сейчас выставлю, а если вы захотите апеллировать и успешно это сделаете, заполню отдельный отрывной.

Пока домашки постепенно проверяются, предлагаю обсудить следующий семестр. Традиционно осенью я читаю продвинутый спецкурс по сложности вычислений для небольшой аудитории. Предлагаю по ссылке https://doodle.com/poll/duvk22hfs36e3xke записаться желающим ходить и выбрать тему. Можно выбирать несколько тем или отмечать вариант "наполовину", кликнув на него два раза. Варианты курсов (если нужны подробности, пишите в чате):
1) Вероятностно проверяемые доказательства. Полное доказательство PCP-теоремы (для этого нужно будет изучить теорию экспандеров), связь с аппроксимацией различных задач оптимизации, в том числе Unique Game Conjecture.
2) Псевдослучайность и дерандомизация. Различные псевдослучайные объекты (в том числе те же экспандеры), обоснование гипотезы BPP=P (генератор Нисана-Вигдерсона, Hardness vs Randomness). Этот курс я читал последние 2 года, так что он будет выбран только при большом перевесе.
3) Вычислительные задачи поиска. Подробно про классы задач поиска (PPAD и другие), связь с теорией игр и экономическими моделями.
4) Рациональные интерактивные доказательства. Подробно про системы доказательств с прувером или пруверами, максимизирующими награду. Доказательство теорем о равенстве соответствующих классов.

Немного о том, как выглядит сегодняшний экзамен:
- Экзамен рассчитан на 3 часа, с 15 до 18
- Можно пользоваться любыми материалами, в т.ч. электронными и поиском в интернете, но нельзя общаться за исключением зум-конференции и телеграм-чата.
- В итоговый вариант включены вопросы на 95 баллов, но скорее всего больше 60 будет трудно успеть набрать. Выбирайте вопросы по тем темам, которые больше нравятся.
- 3 задачи общей стоимостью 23 балла требуют записи решения
- Остальные требуют только ответа и бывают такого типа:
— упорядочить сложностные классы по вложению. Оценивается пропорционально числу верно указанных мест для классов
— классифицировать данную задачу (выбрать минимальный класс из предложенных, в который она входит)
— выбрать из списка верные вариации определения того или иного класса или верные утверждения из предложенных. Тут за каждый верный ответ даются положительные баллы, за каждый неверный отрицательные. Если не отметить ничего, будет 0, если отметить всё, то тоже будет 0. В минус сумма не уходит.
— задачи с числовым ответом. В условии сказано, с какой точностью нужно ввести ответ, за меньшую точность могут даваться частичные баллы.
— несколько вопросов, не укладывающиеся в эту классификацию

Экзамен будет происходить через видеоконференцию Zoom по ссылке https://us02web.zoom.us/j/84512195906?pwd=aVY2a0hkODlQWDdERVcrek1ma0JGZz09, выполнять задания надо в LMS.

Идентификатор конференции: 845 1219 5906
Пароль: 500287

Конференция откроется с 14:45, экзамен в LMS автоматически откроется в 15.

Поскольку у меня 8-го утром будет ещё один экзамен и учитывая результаты опроса, я поставил начало контрольной 8 июня на 15 часов. Я сделал в LMS отдельную группу для написания контрольной и внёс туда всех, кто есть в ведомости, кроме Михаила Бочко, которого почему-то нет в системе. Если вы хотите писать к/р, но не попали в группу, пишите. Также я сделал возможность загрузить домашнее задание в LMS, и это предпочтительный вариант. Дедлайн - 23:59 9 июня, потом по 1 баллу штрафа за каждый час опоздания.
Сама контрольная будет состоять из большого количества несложных вопросов, требующих выбора из вариантов ответа или короткого/числового ответа, а также из 2-3 задач, требующих записи решения. Максимально возможное число баллов будет порядка 80, время на выполнение - 3 часа.

Подготовил домашнее задание. Ориентировочный срок - 27-29 мая, примерно тогда же предлагаю сделать онлайн-контрольную. Принимаются предложения о точных дате и времени.

Итоговые слайды со всеми пометками