Класс IP
| Определение: |
Интерактивным протоколом, разрешающим язык [math]L[/math], называется абстрактная машина (см. рис. 1), моделирующая вычисления как обмен сообщениями между двумя программами (Prover и Verifier, далее [math]P[/math] и [math]V[/math] соответственно), такими, что
- [math]P[/math] заинтересован в том, чтобы [math]V[/math] решил, что слово [math]x[/math] принадлежит языку;
- [math]P[/math] не ограничен в вычислительной мощности;
- [math]V[/math] заинтересован установить, действительно ли слово [math]x[/math] принадлежит языку;
- [math]V[/math] — вероятностная машина Тьюринга;
- [math]V[/math] ограничен полиномиальным временем работы.
|
Рис. 1. Схема интерактивного протокола.
Интерактивные протоколы делятся на два типа в зависимости от доступа [math]P[/math] к вероятностной ленте [math]V[/math]:
- public coins — [math]P[/math] может видеть вероятностную ленту [math]V[/math];
- private coins — [math]P[/math] не может видеть вероятностную ленту [math]V[/math].
| Определение: |
[math]IP[f] = \{L|\exists \langle V, P \rangle : [/math]
- [math]P[/math] не имеет доступа к вероятностной ленте [math]V[/math] (private coins);
- [math] \forall x \in L \Rightarrow P(V(x) = 1) \ge \frac{2}{3} [/math];
- [math] \forall x \notin L \Rightarrow P(V(x) = 1) \le \frac{1}{3} [/math];
- число раундов интерактивного протокола [math] O(f(n)), n = |x| [/math].
|
Язык AM (Arthur–Merlin games) отличается от IP лишь тем, что [math]P[/math] может видеть вероятностную ленту [math]V[/math].
| Определение: |
[math]AM[f] = \{L|\exists \langle V, P \rangle : [/math]
- [math]P[/math] может читать вероятностную ленту [math]V[/math] (public coins);
- [math] \forall x \in L \Rightarrow P(V(x) = 1) \ge \frac{2}{3} [/math];
- [math] \forall x \notin L \Rightarrow P(V(x) = 1) \le \frac{1}{3} [/math];
- число раундов интерактивного протокола [math] O(f(n)), n = |x| [/math].
|
| Определение: |
| Если для интерактивного протокола выполняется [math] \forall x \in L \Rightarrow P(V(x) = 1) = 1 [/math], то говорят, что он обладает свойством completeness (его можно достичь). |
| Определение: |
| Если для интерактивного протокола выполняется [math] \forall x \notin L \Rightarrow P(V(x) = 1) = 0 [/math], то говорят, что он обладает свойством soundness (его нельзя достичь). |
| Теорема: |
[math]\mathrm{BPP} \subset \mathrm{IP[0]}[/math] |
| Доказательство: |
| [math]\triangleright[/math] |
|
[math]V[/math] сам по себе является вероятностной машиной Тьюринга и поэтому может разрешить язык из [math]\mathrm{BPP}[/math] не прибегая к общению с [math]P[/math]. |
| [math]\triangleleft[/math] |
| Теорема: |
[math]\mathrm{NP} \subset \mathrm{IP[1]}[/math] |
| Доказательство: |
| [math]\triangleright[/math] |
|
Для разрешения языка из [math]\mathrm{NP}[/math] будем использовать следующий протокол:
[math]V[/math] будет проверять на принадлежность слова [math]x[/math] используя сертификат, который он запросит у [math]P[/math]. Так как [math]P[/math] не ограничен в вычислительной мощности, он может подобрать подходящий сертификат и именно его и сообщит, так как он заинтересован в том, чтобы [math]V[/math] принял слово. Для этого требуется лишь один раунд интерактивного протокола. |
| [math]\triangleleft[/math] |
| Определение: |
| [math]GNI[/math] расшифровывается как Graph Non Isomorphism. Это язык пар неизоморфных друг другу графов.
[math]GNI=\{ \langle G, H \rangle, [/math] графы [math]G[/math] и [math]H[/math] не изоморфны [math]\}[/math] |
| Теорема: |
[math]GNI \in \mathrm{IP[1]}[/math] |
| Доказательство: |
| [math]\triangleright[/math] |
|
Будем использовать следующий алгоритм для [math]V[/math]:
- Возьмём случайное число [math]i \in \{0, 1\}[/math] и случайную перестановку [math]\pi[/math] с вероятностной ленты;
- Создадим новый граф, перемешав вершины графа c номером [math]i[/math] перестановкой [math]\pi[/math];
- Перешлём [math]P[/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 GNI[/math]. Тогда [math]G[/math] и [math]H[/math] неизоморфны и [math]P[/math] сможет определить какой граф был перемешан [math]V[/math]. Таким образом, [math]P[/math] сможет два раза подряд вернуть правильный ответ и в итоге [math]V[/math] вернёт 1.
- [math] \langle G, H \rangle \notin GNI[/math]. Тогда [math]G[/math] и [math]H[/math] изоморфны и [math]P[/math] не сможет определить какой граф был перемешан [math]V[/math]. Так как [math]P[/math] заинтересован в том, чтобы [math]V[/math] принял слово, ему необходимо угадать правильный ответ (иначе [math]V[/math] просто вернёт [math]0[/math]). Вероятность того, что [math]V[/math] примет слово [math]x[/math], когда оно не принадлежит языку (то есть [math]P[/math] два раза подряд верно угадает номер графа), равна [math]\frac{1}{4}[/math].
Таким образом, построенный протокол удовлетворяет условию теоремы. |
| [math]\triangleleft[/math] |
