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