#дневниклекций
В прошлый раз, 13 февраля, на лекции прошли вот что (если что важное забыл перечислить, дополняйте):
- максимально общее определение интерактивной системы доказательств
- определение классов MA и AM
- амплификация в MA, вложение MA в AM.
- теорема о коллапсе AM-иерархии и теорема об ускорении: формулировки и идеи доказательства
- вложение MA и AM в полиномиальную иерархию: идея доказательства, формально наличие нужных сдвигов не доказывали
- протокол Голдвассер-Сипсера с общими случайными битами для задачи о неизоморфизме графов: идея сводимости к проверке размера множества и идея хеширования

Сегодня будем подробнее разбираться с этим протоколом, потом перейдём к IP=PSPACE