Изменения

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

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

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

<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 \exists P(: \mathitmathbb{Verifier^{Prover}P}(x) = 1) \geqslant \frac{2}V_{3} </tex>;<br/># <tex> \forall x \notin L \Rightarrow P(\mathit{Verifier^{Prover}}(x) = 1) \leqslant geqslant \frac{1}{3} alpha </tex>;<br/># число раундов интерактивного протокола , то говорят, что он обладает свойством ''' completeness ''' равным <tex> O(f(n)), n = |x|\}alpha </tex>.<br/>

|definition = Если для интерактивного протокола выполняется <tex>\mathrm{IP}=forall x \notin L \Rightarrow \bigcupforall P : \limits_mathbb{pP}(n) \in poly} \mathrmV_{IPP} [p(nx) = 1)] \leqslant 1 - \alpha </tex>, то говорят, что он обладает свойством ''' soundness ''' равным <tex> \alpha </tex>.}}Если soundeness равно <tex> 1 </tex>, это означет, что если утверждение ложно, то никакой <tex>P</tex> не может убедить <tex>V</tex>, что утверждение истино. Свойство completeness можно достичь, а soundness достичь нельзя. 

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

|definition = <tex>\mathrm{AMIP}=\bigcup\limits_{p(n) \in poly} \mathrm{AMIP} [p(n)] </tex>

Если для интерактивного протокола выполняется <tex> \forall x mathrm{AM}[f] = \in {L \Rightarrow mid \exists </tex> интерактивный протокол <tex>\langle P, V \rangle : </tex># <tex>P</tex> может читать вероятностную ленту <tex>V</tex> (\mathitpublic coins);# completeness равно <tex> 2/{Verifier^3} </tex>;# soundeness равно <tex> 2 /{Prover3}}(x) = 1) = 1 </tex>, то говорят, что он обладает свойством ;# число раундов интерактивного протокола <btex> completeness O(f(n)), n = |x|\}</btex>.

|definition =Если для интерактивного протокола выполняется <tex> \forall x mathrm{AM}=\notin L bigcup\Rightarrow Plimits_{p(n) \mathitin poly} \mathrm{Verifier^{Prover}AM}[p(xn) = 1) = 0 ] </tex>, то говорят, что он обладает свойством <b> soundness </b>.}} Свойство completeness можно достичь, а soundness достичь нельзя.

|statement=<tex>\mathrm{BPP} </tex> <tex>\subset \mathrm{IP}[0]</tex>.

<tex>\mathit{Verifier}V</tex> сам по себе является вероятностной машиной Тьюринга и поэтому может разрешить [[Классы_BPP_и_PP|язык из <tex>\mathrm{BPP}</tex> ]] не прибегая к общению с <tex>\mathit{Prover}P</tex>.

<tex>\mathit{Verifier}P</tex> будет проверять на принадлежность слова <tex>x</tex> языку, используя сертификат, который он запросит у <tex>\mathit{Prover}P</tex>. Так как <tex>\mathit{Prover}P</tex> не ограничен в вычислительной мощности, он может подобрать подходящий сертификат и именно его и сообщит, так как он заинтересован в том, чтобы <tex>\mathit{Verifier}V</tex> принял слово. Для этого требуется лишь один раунд интерактивного протокола.