Изменения

<b>Интерактивным протоколом</b>, разрешающим язык <tex>L</tex>, называется абстрактная машина (см. рисунок), моделирующая вычисления как обмен сообщениями между двумя программами (Prover и Verifier, далее <tex>P\mathit{Prover}</tex> и <tex>V\mathit{Verifier}</tex> соответственно), такими, что# <tex>P\mathit{Prover}</tex> заинтересован в том, чтобы <tex>V\mathit{Verifier}</tex> решил, что слово <tex>x</tex> принадлежит языку;# <tex>P\mathit{Prover}</tex> не ограничен в вычислительной мощности;# <tex>V\mathit{Verifier}</tex> заинтересован установить, действительно ли слово <tex>x</tex> принадлежит языку;# <tex>V\mathit{Verifier}</tex> — [[Вероятностные вычисления. Вероятностная машина Тьюринга|вероятностная машина Тьюринга]];# <tex>V\mathit{Verifier}</tex> ограничен полиномиальным временем работы.

<tex>V\mathit{Verifier}</tex>, обменивающийся сообщениями с <tex>P\mathit{Prover}</tex>, будем обозначать <tex>V\mathit{Verifier^{PProver}}</tex>.

Интерактивные протоколы делятся на два типа в зависимости от доступа <tex>P\mathit{Prover}</tex> к вероятностной ленте <tex>V\mathit{Verifier}</tex>:# <b> public coins </b> — <tex>P\mathit{Prover}</tex> может видеть вероятностную ленту <tex>V\mathit{Verifier}</tex>;# <b> private coins </b> — <tex>P\mathit{Prover}</tex> <b>не</b> может видеть вероятностную ленту <tex>V\mathit{Verifier}</tex>.

<tex>\mathrm{IP}[f] = \{L\bigm|\exists \langle V\mathit{Verifier}, P \mathit{Prover} \rangle : </tex> <br/># <tex>P\mathit{Prover}</tex> не имеет доступа к вероятностной ленте <tex>V\mathit{Verifier}</tex> (private coins);# <tex> \forall x \in L \Rightarrow P(V\mathit{Verifier^{PProver}}(x) = 1) \ge \frac{2}{3} </tex>;<br/># <tex> \forall x \notin L \Rightarrow P(V\mathit{Verifier^{PProver}}(x) = 1) \le \frac{1}{3} </tex>;<br/>

Язык <tex>\mathrm{AM}</tex> (<i>Arthur–Merlin games</i>) отличается от <tex>\mathrm{IP}</tex> лишь тем, что <tex>P\mathit{Prover}</tex> может видеть вероятностную ленту <tex>V\mathit{Verifier}</tex>.

<tex>\mathrm{AM}[f] = \{L\bigm|\exists \langle V\mathit{Verifier}, P \mathit{Prover} \rangle : </tex> <br/># <tex>P\mathit{Prover}</tex> может читать вероятностную ленту <tex>V\mathit{Verifier}</tex> (public coins);# <tex> \forall x \in L \Rightarrow P(V\mathit{Verifier^{PProver}}(x) = 1) \ge \frac{2}{3} </tex>;<br/># <tex> \forall x \notin L \Rightarrow P(V\mathit{Verifier^{PProver}}(x) = 1) \le \frac{1}{3} </tex>;<br/>

Если для интерактивного протокола выполняется <tex> \forall x \in L \Rightarrow P(V\mathit{Verifier^{PProver}}(x) = 1) = 1 </tex>, то говорят, что он обладает свойством <b> completeness </b>.

Если для интерактивного протокола выполняется <tex> \forall x \notin L \Rightarrow P(V\mathit{Verifier^{PProver}}(x) = 1) = 0 </tex>, то говорят, что он обладает свойством <b> soundness </b>.