Вы здесь

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

Лекция
Партнёр:
Предмет:
Дата записи:
21.03.13
Дата публикации:
21.03.13
Код для блога:

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

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

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

Другие лекции курса

11