#дневниклекций
В четверг доказывали теорему Голдвассер-Сипсера для задачи GNI и начали IP=PSPACE. Вот что прошли:
- Напоминание, откуда берётся множество S, размер которого связан с неизоморфизмом графов. Идея хеширование.
- Определение семейства попарно независимых хеш-функций. Эквивалентность двух вариантов.
- Обсуждение арифметики в поле из 2^n элементов и задачи поиска неприводимого многочлена.
- Построение необходимого семейства хеш-функций как линейных функций в поле из 2^n элементов.
- Подбор параметров и конструкция протокола на базе семейства хеш-функций. Доказательство его корректности через попарную независимость.
- История открытия IP=PSPACE через переписку по имейлу.
- Идея арифметизации: преобразование логической формулы в многочлен малой степени.
- Построение интерактивного протокола для задачи о тавтологичности 3-ДНФ.

В следующий раз построим общий протокол IP=PSPACE.