40
правок
Изменения
Нет описания правки
<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/>.
}}
<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/>.
}}
|proof=
Будем использовать следующий протокол:
# <tex>V</tex> возьмёт случайное число <tex>i \in \{0, 1\}</tex> и случайную перестановку <tex>π</tex> с вероятностной ленты;<br/># <tex>V</tex> создаст новый граф, перемешав вершины графа номер <tex>i</tex> перестановкой <tex>π</tex>;<br/># <tex>V</tex> перешлёт <tex>P</tex> полученный граф с вопросом, из какого из исходных графов он был получен;<br/>
# <tex>V</tex> получив ответ, сравнит его с правильным ответом — числом <tex>i</tex>.
}}
