Интерактивные протоколы. Класс IP. Класс AM — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
Строка 69: Строка 69:
 
|proof=
 
|proof=
 
Будем использовать следующий протокол:
 
Будем использовать следующий протокол:
# <tex>V</tex> возьмёт случайное число <tex>i \in \{0, 1\}</tex> и случайную перестановку <tex>π</tex> с вероятностной ленты; <br/>
+
# <tex>V</tex> возьмёт случайное число <tex>i \in \{0, 1\}</tex> и случайную перестановку <tex>\pi</tex> с вероятностной ленты; <br/>
# <tex>V</tex> создаст новый граф, перемешав вершины графа номер <tex>i</tex> перестановкой <tex>π</tex>; <br/>
+
# <tex>V</tex> создаст новый граф, перемешав вершины графа номер <tex>i</tex> перестановкой <tex>\pi</tex>; <br/>
 
# <tex>V</tex> перешлёт <tex>P</tex> полученный граф с вопросом, из какого из исходных графов он был получен; <br/>
 
# <tex>V</tex> перешлёт <tex>P</tex> полученный граф с вопросом, из какого из исходных графов он был получен; <br/>
 
# <tex>V</tex> получив ответ, сравнит его с правильным ответом — числом <tex>i</tex>.
 
# <tex>V</tex> получив ответ, сравнит его с правильным ответом — числом <tex>i</tex>.
 
}}
 
}}

Версия 00:26, 1 июня 2012

Класс IP

Определение:
Интерактивным протоколом, разрешающим язык [math]L[/math], называется абстрактная машина (см. рис. 1), моделирующая вычисления как обмен сообщениями между двумя программами ([math]Prover[/math] и [math]Verifier[/math], далее [math]P[/math] и [math]V[/math] соответственно), такими, что
  1. [math]P[/math] убеждает [math]V[/math] в том, что слово [math]x[/math] принадлежит языку;
  2. [math]P[/math] не ограничен в вычислительной мощности;
  3. [math]V[/math] — вероятностная машина Тьюринга;
  4. [math]V[/math] ограничен полиномиальным временем работы.


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

Интерактивные протоколы делятся на два типа в зависимости от доступа [math]P[/math] к вероятностной ленте [math]V[/math]:

  1. public coins [math]P[/math] может видеть вероятностную ленту [math]V[/math];
  2. private coins [math]P[/math] не может видеть вероятностную ленту [math]V[/math].


Определение:
[math]IP[f] = \{L|\exists \langle V, P \rangle : [/math]
  1. [math]P[/math] не имеет доступа к вероятностной ленте [math]V[/math] (private coins);
  2. [math] \forall x \in L \Rightarrow P(V(x) = 1) \ge \frac{2}{3} [/math];
  3. [math] \forall x \notin L \Rightarrow P(V(x) = 1) \le \frac{1}{3} [/math];
  4. число раундов интерактивного протокола [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]
  1. [math]P[/math] может читать вероятностную ленту [math]V[/math] (public coins);
  2. [math] \forall x \in L \Rightarrow P(V(x) = 1) \ge \frac{2}{3} [/math];
  3. [math] \forall x \notin L \Rightarrow P(V(x) = 1) \le \frac{1}{3} [/math];
  4. число раундов интерактивного протокола [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]

Будем использовать следующий протокол:

  1. [math]V[/math] возьмёт случайное число [math]i \in \{0, 1\}[/math] и случайную перестановку [math]\pi[/math] с вероятностной ленты;
  2. [math]V[/math] создаст новый граф, перемешав вершины графа номер [math]i[/math] перестановкой [math]\pi[/math];
  3. [math]V[/math] перешлёт [math]P[/math] полученный граф с вопросом, из какого из исходных графов он был получен;
  4. [math]V[/math] получив ответ, сравнит его с правильным ответом — числом [math]i[/math].
[math]\triangleleft[/math]