40
правок
Изменения
Нет описания правки
# число раундов интерактивного протокола <tex> O(f(n)), n = |x| </tex><br/>
}}
Язык AM (<i>Arthur–Merlin games</i>) отличается от IP лишь тем, что <tex>P</tex> может видеть вероятностную ленту <tex>V</tex>.
{{Определение
|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/>
}}
{{Определение
