Интерактивные протоколы. Класс IP. Класс AM

Определения

Определение:

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

Схема интерактивного протокола.

[math]\mathit{Verifier}[/math], обменивающийся сообщениями с [math]\mathit{Prover}[/math], будем обозначать [math]\mathit{Verifier^{Prover}}[/math].

Интерактивные протоколы делятся на два типа в зависимости от доступа [math]\mathit{Prover}[/math] к вероятностной ленте [math]\mathit{Verifier}[/math]:

1. public coins — [math]\mathit{Prover}[/math] может видеть вероятностную ленту [math]\mathit{Verifier}[/math];
2. private coins — [math]\mathit{Prover}[/math] не может видеть вероятностную ленту [math]\mathit{Verifier}[/math].

Определение:

[math]\mathrm{IP}[f] = \{L\bigm|\exists \langle \mathit{Verifier}, \mathit{Prover} \rangle : [/math] [math]\mathit{Prover}[/math] не имеет доступа к вероятностной ленте [math]\mathit{Verifier}[/math] (private coins); [math] \forall x \in L \Rightarrow P(\mathit{Verifier^{Prover}}(x) = 1) \geqslant \frac{2}{3} [/math]; [math] \forall x \notin L \Rightarrow P(\mathit{Verifier^{Prover}}(x) = 1) \leqslant \frac{1}{3} [/math]; число раундов интерактивного протокола [math] O(f(n)), n = |x|\}[/math].

Определение:

[math]\mathrm{IP}=\bigcup\limits_{p(n) \in poly} \mathrm{IP} [p(n)] [/math]

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

Определение:

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

Определение:

[math]\mathrm{AM}=\bigcup\limits_{p(n) \in poly} \mathrm{AM} [p(n)] [/math]

Определение:

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

Определение:

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

Свойство completeness можно достичь, а soundness достичь нельзя.

Соотношения с другими классами теории сложности

Теорема:

[math]\mathrm{BPP} \subset \mathrm{IP}[0][/math].

Доказательство:

[math]\triangleright[/math]

[math]\mathit{Verifier}[/math] сам по себе является вероятностной машиной Тьюринга и поэтому может разрешить язык из [math]\mathrm{BPP}[/math] не прибегая к общению с [math]\mathit{Prover}[/math].

[math]\triangleleft[/math]

Теорема:

[math]\mathrm{NP} \subset \mathrm{IP}[1][/math].

Доказательство:

[math]\triangleright[/math]

Для разрешения языка из [math]\mathrm{NP}[/math] будем использовать следующий протокол: [math]\mathit{Verifier}[/math] будет проверять на принадлежность слова [math]x[/math] используя сертификат, который он запросит у [math]\mathit{Prover}[/math]. Так как [math]\mathit{Prover}[/math] не ограничен в вычислительной мощности, он может подобрать подходящий сертификат и именно его и сообщит, так как он заинтересован в том, чтобы [math]\mathit{Verifier}[/math] принял слово. Для этого требуется лишь один раунд интерактивного протокола.

[math]\triangleleft[/math]

Язык GNI

Определение:

[math]\mathrm{GNI}[/math] расшифровывается как Graph Non Isomorphism. Это язык пар неизоморфных друг другу графов. [math]\mathrm{GNI}=\{ \langle G, H \rangle, [/math] графы [math]G[/math] и [math]H[/math] не изоморфны [math]\}[/math].

Теорема:

[math]\mathrm{GNI} \in \mathrm{IP}[1][/math].

Доказательство:

[math]\triangleright[/math]

Будем использовать следующий алгоритм для [math]\mathit{Verifier}[/math]: Возьмём случайное число [math]i \in \{0, 1\}[/math] и случайную перестановку [math]\pi[/math] с вероятностной ленты; Создадим новый граф, перемешав вершины графа c номером [math]i[/math] перестановкой [math]\pi[/math]; Перешлём [math]\mathit{Prover}[/math] полученный граф с просьбой определить, из какого из исходных графов он был получен; Получив ответ, сравним его с правильным ответом — числом [math]i[/math]; Если полученный ответ не совпадёт с [math]i[/math], то вернём [math]0[/math]; Иначе повторим первые пять шагов ещё раз и перейдём к последнему шагу; Если мы ещё не вернули [math]0[/math], то вернём [math]1[/math]. Покажем, что это удовлетворяет ограничениям на [math]\mathrm{IP}[1][/math]. Во-первых, очевидно, что число раундов не превосходит двух. Рассмотрим теперь случаи [math] \langle G, H \rangle \in \mathrm{GNI}[/math]. Тогда [math]G[/math] и [math]H[/math] неизоморфны и [math]\mathit{Prover}[/math] сможет определить какой граф был перемешан [math]\mathit{Verifier}[/math]. Таким образом, [math]\mathit{Prover}[/math] сможет два раза подряд вернуть правильный ответ и в итоге [math]\mathit{Verifier}[/math] вернёт 1. [math] \langle G, H \rangle \notin \mathrm{GNI}[/math]. Тогда [math]G[/math] и [math]H[/math] изоморфны и [math]\mathit{Prover}[/math] не сможет определить какой граф был перемешан [math]\mathit{Verifier}[/math]. Так как [math]\mathit{Prover}[/math] заинтересован в том, чтобы [math]\mathit{Verifier}[/math] принял слово, ему необходимо угадать правильный ответ (иначе [math]\mathit{Verifier}[/math] просто вернёт [math]0[/math]). Вероятность того, что [math]\mathit{Verifier}[/math] примет слово [math]x[/math], когда оно не принадлежит языку (то есть [math]\mathit{Prover}[/math] два раза подряд верно угадает номер графа), равна [math]\frac{1}{4}[/math]. Таким образом, построенный протокол удовлетворяет условию теоремы.

[math]\triangleleft[/math]

См. также

• Вероятностные вычисления. Вероятностная машина Тьюринга
• Классы NP и Σ₁