Изменения

Классом <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 P\forall Q : Pr(V^{Q}(x)=1)\le \frac{1}{3} \ \forall Q </tex>

<tex>'''NP \subset ''' ⊂ '''IP'''[1] </tex>, <tex>'''BPP \subset ''' ⊂ '''IP'''[0] </tex> 

Первое утверждение верно, так как определить, принадлежит ли слово языку , можно за один запрос от . <tex>V</tex> посылает запрос к <tex>P</tex>и в ответ получает сертификат, если слово принадлежит языку. Если слово не принадлежит языку, то сертификата не существует, а значит <tex>VP</tex> посылает запрос к не может его послать. <tex>P</tex> и хочет убедить <tex>V</tex> в ответ либо получает сертификат(если том, что слово принадлежит языку), либо поэтому пришлет сертификат в случае его существования. Второе утверждение очевидно, так как для проверки принадлежности слова к языку из [[Сложностный класс BPP|'''BPP''']] хватает вычислительной мощности <tex>V</tex>, и запросов к <tex>P</tex> делать не получает(если слово не принадлежит языку)нужно.

Второе утверждение очевидно==Замечание==На самом деле '''NP''' ⊂ '''dIP'''[1], так как для проверки принадлежности к где '''dIP'''[1] - аналог '''IP'''[Сложностный класс BPP|BPP1]] хватает вычислительной мощности <tex>V</tex>, и запросов к за исключением того, что <tex>V</tex> делать не нужноиз '''dIP'''[1] - детерминированная машина Тьюринга.

<tex>I '''IP''' = '''IP'''[poly]</tex> - класс языков, распознаваемых с помощью интерактивного протокола доказательства с полиномиальным числом запросов от <tex>V</tex> к <tex>P</tex>.