1632
правки
Изменения
м
rollbackEdits.php mass rollback
==Определение==
Классом <tex>'''IP'''[f(n)]</tex> ('''IP ''' = interactive proof) называется множество языков, распознаваемых с помощью интерактивного протокола доказательства. При этом:
1) <tex>x \in L \Rightarrow \exists P : Pr(V^{P}(x)=1)\ge \frac{2}{3} \ </tex> , где <tex>Pr(V^{P}(x)=1)</tex> - вероятность того, что <tex>P</tex> убедит <tex>V</tex> допуститить <tex>x</tex>
2) <tex>\ x \notin L \Rightarrow \forall Q : Pr(V^{Q}(x)=1)\le \frac{1}{3} </tex>
==Теорема==
'''NP ''' ⊂ '''IP'''[1], ''', BPP'''BPP ⊂ '''IP'''[0]'''
==Доказательство==
==Замечание==
На самом деле '''NP ''' ⊂ '''dIP'''[1], где ''', где dIP'''dIP[1]- аналог ''' - аналог IP'''IP[1]''', за исключением того, что '''<tex>V</tex> из ''' из dIP'''dIP[1]''' - детерминированная машина Тьюринга.
==Определение==
'''IP ''' = '''IP'''[poly]''' - класс языков, распознаваемых с помощью интерактивного протокола доказательства с полиномиальным числом запросов от <tex>V</tex> к <tex>P</tex>.
