Сложность вычислений и основы криптографии. Лекция 3
ЛекцияПартнёр:
Предмет:
- Computer Science
Лектор:
Курс лекций:
Дата записи:
07.03.13
Дата публикации:
07.03.13
Код для блога:
Игры Артура и Мерлина
Универсальное семейство попарно независимых хеш-функций. Конструкция. Протокол для нижней оценки на размер множества. Публичные и скрытые случайные биты, игры Мерлина и Артура. Классы AM и MA. GNI содержится в AM. Теорема Голдвассера-Сипсера (без доказательства). Из NP-полноты изоморфизма графов следует, что полиномиальная иерархия схлопывается на 2 уровне.
Страница лекции на сайте Computer Science Center.
Другие лекции курса
11