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

Материал из Викиконспекты
Перейти к: навигация, поиск
м
Строка 19: Строка 19:
 
{{Определение
 
{{Определение
 
|definition =
 
|definition =
<tex>IP[f] = \{L|\exists \langle V, P \rangle : </tex> <br/>
+
<tex>\mathrm{IP[f]} = \{L\bigm|\exists \langle V, P \rangle : </tex> <br/>
 
# <tex>P</tex> не имеет доступа к вероятностной ленте <tex>V</tex> (private coins);
 
# <tex>P</tex> не имеет доступа к вероятностной ленте <tex>V</tex> (private coins);
 
# <tex> \forall x \in L \Rightarrow P(V(x) = 1) \ge \frac{2}{3} </tex>;<br/>
 
# <tex> \forall x \in L \Rightarrow P(V(x) = 1) \ge \frac{2}{3} </tex>;<br/>
Строка 26: Строка 26:
 
}}
 
}}
  
Язык AM (<i>Arthur–Merlin games</i>) отличается от IP лишь тем, что <tex>P</tex> может видеть вероятностную ленту <tex>V</tex>.
+
Язык \mathrm{AM} (<i>Arthur–Merlin games</i>) отличается от \mathrm{IP} лишь тем, что <tex>P</tex> может видеть вероятностную ленту <tex>V</tex>.
 
{{Определение
 
{{Определение
 
|definition =
 
|definition =
<tex>AM[f] = \{L|\exists \langle V, P \rangle : </tex> <br/>
+
<tex>\mathrm{AM[f]} = \{L\bigm|\exists \langle V, P \rangle : </tex> <br/>
 
# <tex>P</tex> может читать вероятностную ленту <tex>V</tex> (public coins);
 
# <tex>P</tex> может читать вероятностную ленту <tex>V</tex> (public coins);
 
# <tex> \forall x \in L \Rightarrow P(V(x) = 1) \ge \frac{2}{3} </tex>;<br/>
 
# <tex> \forall x \in L \Rightarrow P(V(x) = 1) \ge \frac{2}{3} </tex>;<br/>
Строка 39: Строка 39:
 
{{Определение
 
{{Определение
 
|definition =
 
|definition =
Если для интерактивного протокола выполняется <tex> \forall x \in L \Rightarrow P(V(x) = 1) = 1 </tex>, то говорят, что он обладает свойством <b> completeness </b> (его можно достичь).
+
Если для интерактивного протокола выполняется <tex> \forall x \in L \Rightarrow P(V(x) = 1) = 1 </tex>, то говорят, что он обладает свойством <b> completeness </b>.
 
}}
 
}}
  
 
{{Определение
 
{{Определение
 
|definition =
 
|definition =
Если для интерактивного протокола выполняется <tex> \forall x \notin L \Rightarrow P(V(x) = 1) = 0 </tex>, то говорят, что он обладает свойством <b> soundness </b> (его нельзя достичь).
+
Если для интерактивного протокола выполняется <tex> \forall x \notin L \Rightarrow P(V(x) = 1) = 0 </tex>, то говорят, что он обладает свойством <b> soundness </b>.
 
}}  
 
}}  
 +
 +
Свойство completeness можно достичь, а soundness достичь нельзя.
  
 
{{Теорема
 
{{Теорема
Строка 62: Строка 64:
 
{{Определение
 
{{Определение
 
|definition=
 
|definition=
<tex>GNI</tex> расшифровывается как Graph Non Isomorphism. Это язык пар неизоморфных друг другу графов.
+
<tex>\mathrm{GNI}</tex> расшифровывается как Graph Non Isomorphism. Это язык пар неизоморфных друг другу графов.
<tex>GNI=\{ \langle G, H \rangle, </tex> графы <tex>G</tex> и <tex>H</tex> не изоморфны <tex>\}</tex>
+
<tex>\mathrm{GNI}=\{ \langle G, H \rangle, </tex> графы <tex>G</tex> и <tex>H</tex> не изоморфны <tex>\}</tex>
 
}}
 
}}
  
 
{{Теорема
 
{{Теорема
|statement=<tex>GNI \in \mathrm{IP[1]}</tex>
+
|statement=<tex>\mathrm{GNI} \in \mathrm{IP[1]}</tex>
 
|proof=
 
|proof=
 
Будем использовать следующий алгоритм для <tex>V</tex>:
 
Будем использовать следующий алгоритм для <tex>V</tex>:
Строка 81: Строка 83:
 
Во-первых, очевидно, что число раундов не превосходит двух. <br/>
 
Во-первых, очевидно, что число раундов не превосходит двух. <br/>
 
Рассмотрим теперь случаи
 
Рассмотрим теперь случаи
* <tex> \langle G, H \rangle \in GNI</tex>. Тогда <tex>G</tex> и <tex>H</tex> неизоморфны и <tex>P</tex> сможет определить какой граф был перемешан <tex>V</tex>. Таким образом, <tex>P</tex> сможет два раза подряд вернуть правильный ответ и в итоге <tex>V</tex> вернёт 1.
+
* <tex> \langle G, H \rangle \in \mathrm{GNI}</tex>. Тогда <tex>G</tex> и <tex>H</tex> неизоморфны и <tex>P</tex> сможет определить какой граф был перемешан <tex>V</tex>. Таким образом, <tex>P</tex> сможет два раза подряд вернуть правильный ответ и в итоге <tex>V</tex> вернёт 1.
* <tex> \langle G, H \rangle \notin GNI</tex>. Тогда <tex>G</tex> и <tex>H</tex> изоморфны и <tex>P</tex> не сможет определить какой граф был перемешан <tex>V</tex>. Так как <tex>P</tex> заинтересован в том, чтобы <tex>V</tex> принял слово, ему необходимо угадать правильный ответ (иначе <tex>V</tex> просто вернёт <tex>0</tex>). Вероятность того, что <tex>V</tex> примет слово <tex>x</tex>, когда оно не принадлежит языку (то есть <tex>P</tex> два раза подряд верно угадает номер графа), равна <tex>\frac{1}{4}</tex>.
+
* <tex> \langle G, H \rangle \notin \mathrm{GNI}</tex>. Тогда <tex>G</tex> и <tex>H</tex> изоморфны и <tex>P</tex> не сможет определить какой граф был перемешан <tex>V</tex>. Так как <tex>P</tex> заинтересован в том, чтобы <tex>V</tex> принял слово, ему необходимо угадать правильный ответ (иначе <tex>V</tex> просто вернёт <tex>0</tex>). Вероятность того, что <tex>V</tex> примет слово <tex>x</tex>, когда оно не принадлежит языку (то есть <tex>P</tex> два раза подряд верно угадает номер графа), равна <tex>\frac{1}{4}</tex>.
 
Таким образом, построенный протокол удовлетворяет условию теоремы.
 
Таким образом, построенный протокол удовлетворяет условию теоремы.
 
}}
 
}}

Версия 01:30, 4 июня 2012

Класс IP

Определение:
Интерактивным протоколом, разрешающим язык [math]L[/math], называется абстрактная машина (см. рис. 1), моделирующая вычисления как обмен сообщениями между двумя программами (Prover и Verifier, далее [math]P[/math] и [math]V[/math] соответственно), такими, что
  1. [math]P[/math] заинтересован в том, чтобы [math]V[/math] решил, что слово [math]x[/math] принадлежит языку;
  2. [math]P[/math] не ограничен в вычислительной мощности;
  3. [math]V[/math] заинтересован установить, действительно ли слово [math]x[/math] принадлежит языку;
  4. [math]V[/math] — вероятностная машина Тьюринга;
  5. [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]\mathrm{IP[f]} = \{L\bigm|\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].


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

Определение:
[math]\mathrm{AM[f]} = \{L\bigm|\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 .


Свойство completeness можно достичь, а 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]\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]V[/math]:

  1. Возьмём случайное число [math]i \in \{0, 1\}[/math] и случайную перестановку [math]\pi[/math] с вероятностной ленты;
  2. Создадим новый граф, перемешав вершины графа c номером [math]i[/math] перестановкой [math]\pi[/math];
  3. Перешлём [math]P[/math] полученный граф с просьбой определить, из какого из исходных графов он был получен;
  4. Получив ответ, сравним его с правильным ответом — числом [math]i[/math];
  5. Если полученный ответ не совпадёт с [math]i[/math], то вернём [math]0[/math];
  6. Иначе повторим первые пять шагов ещё раз и перейдём к последнему шагу;
  7. Если мы ещё не вернули [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]P[/math] сможет определить какой граф был перемешан [math]V[/math]. Таким образом, [math]P[/math] сможет два раза подряд вернуть правильный ответ и в итоге [math]V[/math] вернёт 1.
  • [math] \langle G, H \rangle \notin \mathrm{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]