Изменения

Перейти к: навигация, поиск

Класс IP

Нет изменений в размере, 16:40, 6 мая 2010
Замечание
==Замечание==
На самом деле '''NP ⊂ dIP[1]''', где '''dIP[1]''' - аналог '''IP[1]''', за исключением того, что <tex>V<\/tex> из '''dIP[1]''' - детерминированная машина Тьюринга.
==Определение==
'''IP = IP[poly]''' - класс языков, распознаваемых с помощью интерактивного протокола доказательства с полиномиальным числом запросов от <tex>V</tex> к <tex>P</tex>.
Анонимный участник

Навигация