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