Изменения
Нет описания правки
{{Определение
|definition =
<tex>\mathrm{IP[f] } = \{L\bigm|\exists \langle V, P \rangle : </tex> <br/>
# <tex>P</tex> не имеет доступа к вероятностной ленте <tex>V</tex> (private coins);
# <tex> \forall x \in L \Rightarrow P(V(x) = 1) \ge \frac{2}{3} </tex>;<br/>
}}
Язык \mathrm{AM } (<i>Arthur–Merlin games</i>) отличается от \mathrm{IP } лишь тем, что <tex>P</tex> может видеть вероятностную ленту <tex>V</tex>.
{{Определение
|definition =
<tex>\mathrm{AM[f] } = \{L\bigm|\exists \langle V, P \rangle : </tex> <br/>
# <tex>P</tex> может читать вероятностную ленту <tex>V</tex> (public coins);
# <tex> \forall x \in L \Rightarrow P(V(x) = 1) \ge \frac{2}{3} </tex>;<br/>
{{Определение
|definition =
Если для интерактивного протокола выполняется <tex> \forall x \in L \Rightarrow P(V(x) = 1) = 1 </tex>, то говорят, что он обладает свойством <b> completeness </b> (его можно достичь).
}}
{{Определение
|definition =
Если для интерактивного протокола выполняется <tex> \forall x \notin L \Rightarrow P(V(x) = 1) = 0 </tex>, то говорят, что он обладает свойством <b> soundness </b> (его нельзя достичь).
}}
Свойство completeness можно достичь, а soundness достичь нельзя.
{{Теорема
{{Определение
|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>:
Во-первых, очевидно, что число раундов не превосходит двух. <br/>
Рассмотрим теперь случаи
* <tex> \langle G, H \rangle \in \mathrm{GNI}</tex>. Тогда <tex>G</tex> и <tex>H</tex> неизоморфны и <tex>P</tex> сможет определить какой граф был перемешан <tex>V</tex>. Таким образом, <tex>P</tex> сможет два раза подряд вернуть правильный ответ и в итоге <tex>V</tex> вернёт 1.* <tex> \langle G, H \rangle \notin \mathrm{GNI}</tex>. Тогда <tex>G</tex> и <tex>H</tex> изоморфны и <tex>P</tex> не сможет определить какой граф был перемешан <tex>V</tex>. Так как <tex>P</tex> заинтересован в том, чтобы <tex>V</tex> принял слово, ему необходимо угадать правильный ответ (иначе <tex>V</tex> просто вернёт <tex>0</tex>). Вероятность того, что <tex>V</tex> примет слово <tex>x</tex>, когда оно не принадлежит языку (то есть <tex>P</tex> два раза подряд верно угадает номер графа), равна <tex>\frac{1}{4}</tex>.
Таким образом, построенный протокол удовлетворяет условию теоремы.
}}
