Изменения
Нет описания правки
<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^{P}(x) = 1) \ge \frac{2}{3} </tex>;<br/># <tex> \forall x \notin L \Rightarrow P(V^{P}(x) = 1) \le \frac{1}{3} </tex>;<br/>
# число раундов интерактивного протокола <tex> O(f(n)), n = |x|\}</tex>.<br/>
}}
<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^{P}(x) = 1) \ge \frac{2}{3} </tex>;<br/># <tex> \forall x \notin L \Rightarrow P(V^{P}(x) = 1) \le \frac{1}{3} </tex>;<br/>
# число раундов интерактивного протокола <tex> O(f(n)), n = |x|\} </tex>.<br/>
}}
{{Определение
|definition =
Если для интерактивного протокола выполняется <tex> \forall x \in L \Rightarrow P(V^{P}(x) = 1) = 1 </tex>, то говорят, что он обладает свойством <b> completeness </b>.
}}
{{Определение
|definition =
Если для интерактивного протокола выполняется <tex> \forall x \notin L \Rightarrow P(V^{P}(x) = 1) = 0 </tex>, то говорят, что он обладает свойством <b> soundness </b>.
}}
Свойство completeness можно достичь, а soundness достичь нельзя.
