Изменения
Нет описания правки
<tex>\mathrm{IP}[f] = \{L\bigm|\exists \langle \mathit{Verifier}, \mathit{Prover} \rangle : </tex> <br/>
# <tex>\mathit{Prover}</tex> не имеет доступа к вероятностной ленте <tex>\mathit{Verifier}</tex> (private coins);
# <tex> \forall x \in L \Rightarrow P(\mathit{Verifier^{Prover}}(x) = 1) \ge geqslant \frac{2}{3} </tex>;<br/># <tex> \forall x \notin L \Rightarrow P(\mathit{Verifier^{Prover}}(x) = 1) \le leqslant \frac{1}{3} </tex>;<br/>
# число раундов интерактивного протокола <tex> O(f(n)), n = |x|\}</tex>.<br/>
}}
<tex>\mathrm{AM}[f] = \{L\bigm|\exists \langle \mathit{Verifier}, \mathit{Prover} \rangle : </tex> <br/>
# <tex>\mathit{Prover}</tex> может читать вероятностную ленту <tex>\mathit{Verifier}</tex> (public coins);
# <tex> \forall x \in L \Rightarrow P(\mathit{Verifier^{Prover}}(x) = 1) \ge geqslant \frac{2}{3} </tex>;<br/># <tex> \forall x \notin L \Rightarrow P(\mathit{Verifier^{Prover}}(x) = 1) \le leqslant \frac{1}{3} </tex>;<br/>
# число раундов интерактивного протокола <tex> O(f(n)), n = |x|\} </tex>.<br/>
}}
