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