Изменения
Нет описания правки
# <tex> \forall x \in L \Rightarrow P(V(x) = 1) \ge \frac{2}{3} </tex>;<br/>
# <tex> \forall x \notin L \Rightarrow P(V(x) = 1) \le \frac{1}{3} </tex>;<br/>
# число раундов интерактивного протокола <tex> O(f(n)), n = |x|\}</tex>.<br/>
}}
# <tex> \forall x \in L \Rightarrow P(V(x) = 1) \ge \frac{2}{3} </tex>;<br/>
# <tex> \forall x \notin L \Rightarrow P(V(x) = 1) \le \frac{1}{3} </tex>;<br/>
# число раундов интерактивного протокола <tex> O(f(n)), n = |x|\} </tex>.<br/>
}}
{{Теорема
|statement=<tex>\mathrm{BPP} \subset \mathrm{IP[0]}</tex>.
|proof=
<tex>V</tex> сам по себе является вероятностной машиной Тьюринга и поэтому может разрешить язык из <tex>\mathrm{BPP}</tex> не прибегая к общению с <tex>P</tex>.
{{Теорема
|statement=<tex>\mathrm{NP} \subset \mathrm{IP[1]}</tex>.
|proof=
Для разрешения языка из <tex>\mathrm{NP}</tex> будем использовать следующий протокол:
|definition=
<tex>\mathrm{GNI}</tex> расшифровывается как Graph Non Isomorphism. Это язык пар неизоморфных друг другу графов.
<tex>\mathrm{GNI}=\{ \langle G, H \rangle, </tex> графы <tex>G</tex> и <tex>H</tex> не изоморфны <tex>\}</tex>.
}}
{{Теорема
|statement=<tex>\mathrm{GNI} \in \mathrm{IP[1]}</tex>.
|proof=
Будем использовать следующий алгоритм для <tex>V</tex>:
