Город: Санкт-Петербург Новосибирск Казань Язык: Русский English

Теорема Тода. Схемная сложность класс PP
Сложность вычислений и основы криптографии


Что: Лекция
Когда: Четверг, 21 марта 2013, 18:30–19:50
Где: ПОМИ РАН

Описание

Классы \( \sharp P \) и \( PP \). Теорема Тода. \( P^{PP} = P^{\sharp P} \). Теорема Вэлианта о \( \sharp P \) -полноте 0/1 перманента (без доказательства). Интерактивное доказательство для перманента. Следствие об интерактивном доказательстве для \( P^{PP} \). Включение \( MA \) в \( PP \). Схемная сложность \( PP \).

Видео