Изменения

<b>Интерактивным протоколом</b> (англ. ''interactive protocol'') <tex> \langle P, V \rangle </tex>, разрешающим язык <tex>L</tex>, называется абстрактная машина (см. рисунок), моделирующая вычисления как обмен сообщениями между двумя программами (где <tex>P</tex> означает <tex>\mathitmathrm{Prover}</tex> и <tex> V </tex> означает <tex>\mathitmathrm{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>\mathitV </tex> и <tex> P </tex> по очереди становятся активными. <tex> V </tex> активизируется первым. В течение работы <tex> V </tex> выполняет вычисления, используя вход, очередные данные с вероятностной ленты и сообщение, пришедшее от <tex> P </tex>, и пишет запрос <tex> P </tex>. Как только <tex> V </tex> написал сообщение, он дизактивируется, и <tex> P </tex> становится активным, если протокол не завершился. Любая машина может завершить выполнение протокола просто не посылая сообщение во время своей активной фазы. <tex> V </tex> принимает (или отвергает) вход, выводит '''true''' (или '''false''') и завершает выполнение протокола. Время работы <tex> V </tex> {{Verifier---}} это сумма времен работы, затраченных <tex> V </tex> в течение активной фазы, и это время ограничено полиномом от длины входа.# <tex>V</tex>, обменивающийся сообщениями с фиксированным <tex>P</tex>\mathit, обозначим <tex>V_{ProverP}</tex>.# Для того, чтобы <tex> V </tex> принял слово, будем обозначать <tex>P</tex> старается максимизировать вероятность <tex>\mathitmathbb{Verifier^P}(V_{ProverP}(x) = 1)</tex>, выбирая нужные ответы на запросы.# Так как мы не ограничиваем <tex>P</tex> в вычислительной мощности, то он может работать бесконечное время, а значит <tex>V</tex> не получит ответ на какой-то вопрос. Но <tex>P</tex> хочет, чтобы <tex> V</tex> принял слово, значит нужно выбирать "хорошие" протоколы, чтобы таких ситуаций не появлялось.# <tex> P </tex> может быть и вероятностной и детерминированной машиной Тьюринга. Так как он имеет неограниченные вычислительные ресурсы, то на каждом ходу он может выбрать такие вероятностные данные и произвести вычисления с ними, что они максимизируют вероятность принятия слова <tex> V </tex>.# С другой стороны, для <tex> V </tex> важно быть вероятностной программой, так как иначе он будет принимать или отвергать слова с вероятностью <tex> 1 </tex>. И пользуясь предыдущим фактом, получим, что <tex> V_{P}</tex> всегда принимает слова из <tex> L </tex>. # Так как <tex> V </tex> может писать и читать полиномиальное число символов, то длина сообщений между <tex> V </tex> и <tex> P </tex> есть полином от длины <tex> x </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] = forall x \{in L\bigm|Rightarrow \exists \langle \mathit{Verifier}, \mathit{Prover} \rangle P : </tex> <br/># <tex>\mathitmathbb{ProverP}</tex> не имеет доступа к вероятностной ленте <tex>\mathit(V_{Verifier}</tex> (private coins);# <tex> \forall x \in L \Rightarrow P(\mathit{Verifier^{Prover}}(x) = 1) \geqslant \frac{2}{3} c </tex>;<br/># <tex> \forall x \notin L \Rightarrow P, то говорят, что он обладает свойством ''' completeness ''' (\mathit{Verifier^{Prover}}(xрусск. ''полнота'') = 1) \leqslant \frac{1}{3} </tex>;<br/># число раундов интерактивного протокола равным <tex> O(f(n)), n = |x|\}c </tex>.<br/>

|definition = Если для интерактивного протокола выполняется <tex>\mathrmforall x \notin L \Rightarrow \forall P : \mathbb{P}(V_{IPP}(x) =1) \bigcup\limits_{pleqslant 1 - s </tex>, то говорят, что он обладает свойством ''' soundness ''' (nрусск. ''достоверность'') \in polyравным <tex> s </tex>.}} Если <tex>s = 1 </tex> ('''perfect soundness''' (русск. ''идеальная достоверность'')), то это означет, что если утверждение ложно, то никакой <tex>P</tex> не может убедить <tex>V</tex>, что утверждение истино. В этом случае мы получем класс <tex> \mathrm{IPNP} [p(n)] </tex>}}. Потому что <tex> x \in L </tex> тогда и только тогда, если существует последовательность случайных вопросов, генерируемых <tex> V </tex>, и последовательность ответов <tex> P </tex>, которые убеждают <tex> V </tex> в том, что <tex> x \in L </tex>. Обратное утверждение сохраняется по предположению идеальной достоверности.

<tex>\mathrm{AMIP}[f] </tex> (''Interactive Polynomial time'') <tex> = \{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);.# <tex> \forall x \in L \Rightarrow P(\mathit{Verifier^{Prover}}(x) = 1) c \geqslant \frac{2}/{3} </tex>;<br/>.# <tex> s \forall x \notin L \Rightarrow P(\mathit{Verifier^{Prover}}(x) = 1) \leqslant \frac{1}geqslant 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> (public coins).# <tex> c \mathitgeqslant 2/{Verifier^3} </tex>.# <tex> s \geqslant 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>.

Для разрешения [[Классы_NP_и_Σ₁#.D0.9E.D0.BF.D1.80.D0.B5.D0.B4.D0.B5.D0.BB.D0.B5.D0.BD.D0.B8.D1.8F.2C_.D1.81.D0.B2.D1.8F.D0.B7.D1.8C_.CE.A3.E2.82.81_.D0.B8_NP|языка из <tex>\mathrm{NP}</tex> ]] будем использовать следующий протокол:<tex>\mathit{Verifier}V</tex> будет проверять на принадлежность слова <tex>x</tex> языку, используя сертификат, который он запросит у <tex>\mathit{Prover}P</tex>. Так как <tex>\mathit{Prover}P</tex> не ограничен в вычислительной мощности, он может подобрать подходящий сертификат и именно его и сообщит, так как он заинтересован в том, чтобы <tex>\mathit{Verifier}V</tex> принял слово. Для этого требуется лишь один раунд интерактивного протокола.

<tex>\mathrm{GNI}</tex> расшифровывается как Graph Non Isomorphism. Это язык пар [[Основные_определения_теории_графов#.D0.9E.D1.80.D0.B8.D0.B5.D0.BD.D1.82.D0.B8.D1.80.D0.BE.D0.B2.D0.B0.D0.BD.D0.BD.D1.8B.D0.B5_.D0.B3.D1.80.D0.B0.D1.84.D1.8B|неизоморфных друг другу графов]].<tex>\mathrm{GNI}=\{ \langle G, H \rangle, \mid </tex> графы <tex>G</tex> и <tex>H</tex> не изоморфны <tex>\}</tex>.

Пусть на вход подали пару графов <tex> \langle G_{0}, G_{1} \rangle </tex> и нужно определить изоморфны ли они.Будем использовать следующий алгоритм для <tex>\mathit{Verifier}V</tex>:# Возьмём случайное число <tex>i \in \{0, 1\}</tex> и [[Комбинаторные_объекты|случайную перестановку ]] <tex>\pi</tex> с вероятностной ленты; <br/># Создадим новый граф<tex> G </tex>, перемешав вершины графа c номером <tex>i</tex> перестановкой <tex>\pi</tex>; <br/>.# Перешлём <tex>\mathit{Prover}P</tex> полученный граф <tex> G </tex> с просьбой определить, из какого из исходных графов он был получен; . Если <tex>G_{0} \ncong G_{1} </tex>, то он может перебрать все перестановки графов <tex> G_{0}, G_{1} </tex>, и так как <tex>G_{0} \ncong G_{1} </tex>, то только одна перестановка только на одном графе даст <tex> G </tex>. Иначе, существуют такие перестановки <tex> \phi, \psi </tex>, что <tex> \phi(G_0) = \psi(G_1) = G </tex>, и <tex> P </tex> никак не сможет определить из какого графа был получен <tex> G </tex>. Тогда <tex> P </tex> просто попытается угадать граф, вернув случайно <tex> 0 </tex> или <tex> 1 <br/tex>.# Получив ответ, сравним его с правильным ответом — числом <tex>i</tex>; <br/>.# Если полученный ответ не совпадёт с <tex>i</tex>, то вернём <tex>0</tex>; <br/>.# Иначе повторим первые пять шагов ещё раз и перейдём к последнему шагу; <br/>.

Во-первых, очевидно, что число раундов не превосходит двух. <br/> Рассмотрим теперь случаидва случая:* <tex> \langle G, H \rangle \in \mathrm{GNI}</tex>. Тогда <tex>G</tex> и <tex>H</tex> неизоморфны и <tex>\mathit{Prover}P</tex> сможет определить какой граф был перемешан <tex>\mathit{Verifier}V</tex>. Таким образом, <tex>\mathit{Prover}P</tex> сможет два раза подряд вернуть правильный ответ и в итоге <tex>\mathit{Verifier}V</tex> вернёт <tex>1</tex>. То есть получили completeness равную <tex> 1</tex>.* <tex> \langle G, H \rangle \notin \mathrm{GNI}</tex>. Тогда <tex>G</tex> и <tex>H</tex> изоморфны и <tex>\mathit{Prover}P</tex> не сможет определить какой граф был перемешан <tex>\mathit{Verifier}V</tex>. Так как <tex>\mathit{Prover}P</tex> заинтересован в том, чтобы <tex>\mathit{Verifier}V</tex> принял слово, ему необходимо угадать правильный ответ (иначе <tex>\mathit{Verifier}V</tex> просто вернёт <tex>0</tex>). Вероятность того, что <tex>\mathit{Verifier}V</tex> примет слово <tex>x</tex>, когда оно не принадлежит языку (то есть <tex>\mathit{Prover}P</tex> два раза подряд верно угадает номер графас вероятностью <tex> 0.5 </tex>), равна <tex>\frac{1}0.25</tex>. Значит soundness равна <tex> 0.75 </tex>, что больше или равно <tex> 2/{43}</tex>.