Сложность вычислений и основы криптографии. Лекция 5

Теорема Тода. Схемная сложность класс PP

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

Страница лекции на сайте Computer Science Center.