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

Материал из Викиконспекты
Перейти к: навигация, поиск
м
Строка 3: Строка 3:
 
{{Определение
 
{{Определение
 
|definition =
 
|definition =
−
<b>Интерактивным протоколом</b>, разрешающим язык <tex>L</tex>, называется абстрактная машина (см. рисунок), моделирующая вычисления как обмен сообщениями между двумя программами (Prover и Verifier, далее <tex>P</tex> и <tex>V</tex> соответственно), такими, что
+
<b>Интерактивным протоколом</b>, разрешающим язык <tex>L</tex>, называется абстрактная машина (см. рисунок), моделирующая вычисления как обмен сообщениями между двумя программами (<tex>\mathit{Prover}</tex> и <tex>\mathit{Verifier}</tex>), такими, что
−
# <tex>P</tex> заинтересован в том, чтобы <tex>V</tex> решил, что слово <tex>x</tex> принадлежит языку;
+
# <tex>\mathit{Prover}</tex> заинтересован в том, чтобы <tex>\mathit{Verifier}</tex> решил, что слово <tex>x</tex> принадлежит языку;
−
# <tex>P</tex> не ограничен в вычислительной мощности;
+
# <tex>\mathit{Prover}</tex> не ограничен в вычислительной мощности;
−
# <tex>V</tex> заинтересован установить, действительно ли слово <tex>x</tex> принадлежит языку;
+
# <tex>\mathit{Verifier}</tex> заинтересован установить, действительно ли слово <tex>x</tex> принадлежит языку;
−
# <tex>V</tex> — [[Вероятностные вычисления. Вероятностная машина Тьюринга|вероятностная машина Тьюринга]];
+
# <tex>\mathit{Verifier}</tex> — [[Вероятностные вычисления. Вероятностная машина Тьюринга|вероятностная машина Тьюринга]];
−
# <tex>V</tex> ограничен полиномиальным временем работы.
+
# <tex>\mathit{Verifier}</tex> ограничен полиномиальным временем работы.
 
}}
 
}}
 
[[Файл:IPS.png|250px|thumb|right|Схема интерактивного протокола.]]
 
[[Файл:IPS.png|250px|thumb|right|Схема интерактивного протокола.]]
  
−
<tex>V</tex>, обменивающийся сообщениями с <tex>P</tex>, будем обозначать <tex>V^{P}</tex>.
+
<tex>\mathit{Verifier}</tex>, обменивающийся сообщениями с <tex>\mathit{Prover}</tex>, будем обозначать <tex>\mathit{Verifier^{Prover}}</tex>.
  
−
Интерактивные протоколы делятся на два типа в зависимости от доступа <tex>P</tex> к вероятностной ленте <tex>V</tex>:
+
Интерактивные протоколы делятся на два типа в зависимости от доступа <tex>\mathit{Prover}</tex> к вероятностной ленте <tex>\mathit{Verifier}</tex>:
−
# <b> public coins </b> — <tex>P</tex> может видеть вероятностную ленту <tex>V</tex>;
+
# <b> public coins </b> — <tex>\mathit{Prover}</tex> может видеть вероятностную ленту <tex>\mathit{Verifier}</tex>;
−
# <b> private coins </b> — <tex>P</tex> <b>не</b> может видеть вероятностную ленту <tex>V</tex>.
+
# <b> private coins </b> — <tex>\mathit{Prover}</tex> <b>не</b> может видеть вероятностную ленту <tex>\mathit{Verifier}</tex>.
  
 
{{Определение
 
{{Определение
 
|definition =
 
|definition =
−
<tex>\mathrm{IP}[f] = \{L\bigm|\exists \langle V, P \rangle : </tex> <br/>
+
<tex>\mathrm{IP}[f] = \{L\bigm|\exists \langle \mathit{Verifier}, \mathit{Prover} \rangle : </tex> <br/>
−
# <tex>P</tex> не имеет доступа к вероятностной ленте <tex>V</tex> (private coins);
+
# <tex>\mathit{Prover}</tex> не имеет доступа к вероятностной ленте <tex>\mathit{Verifier}</tex> (private coins);
−
# <tex> \forall x \in L \Rightarrow P(V^{P}(x) = 1) \ge \frac{2}{3} </tex>;<br/>
+
# <tex> \forall x \in L \Rightarrow P(\mathit{Verifier^{Prover}}(x) = 1) \ge \frac{2}{3} </tex>;<br/>
−
# <tex> \forall x \notin L \Rightarrow P(V^{P}(x) = 1) \le \frac{1}{3} </tex>;<br/>
+
# <tex> \forall x \notin L \Rightarrow P(\mathit{Verifier^{Prover}}(x) = 1) \le \frac{1}{3} </tex>;<br/>
 
# число раундов интерактивного протокола <tex> O(f(n)), n = |x|\}</tex>.<br/>
 
# число раундов интерактивного протокола <tex> O(f(n)), n = |x|\}</tex>.<br/>
 
}}
 
}}
Строка 30: Строка 30:
 
}}
 
}}
  
−
Язык <tex>\mathrm{AM}</tex> (<i>Arthur–Merlin games</i>) отличается от <tex>\mathrm{IP}</tex> лишь тем, что <tex>P</tex> может видеть вероятностную ленту <tex>V</tex>.
+
Язык <tex>\mathrm{AM}</tex> (<i>Arthur–Merlin games</i>) отличается от <tex>\mathrm{IP}</tex> лишь тем, что <tex>\mathit{Prover}</tex> может видеть вероятностную ленту <tex>\mathit{Verifier}</tex>.
 
{{Определение
 
{{Определение
 
|definition =
 
|definition =
−
<tex>\mathrm{AM}[f] = \{L\bigm|\exists \langle V, P \rangle : </tex> <br/>
+
<tex>\mathrm{AM}[f] = \{L\bigm|\exists \langle \mathit{Verifier}, \mathit{Prover} \rangle : </tex> <br/>
−
# <tex>P</tex> может читать вероятностную ленту <tex>V</tex> (public coins);
+
# <tex>\mathit{Prover}</tex> может читать вероятностную ленту <tex>\mathit{Verifier}</tex> (public coins);
−
# <tex> \forall x \in L \Rightarrow P(V^{P}(x) = 1) \ge \frac{2}{3} </tex>;<br/>
+
# <tex> \forall x \in L \Rightarrow P(\mathit{Verifier^{Prover}}(x) = 1) \ge \frac{2}{3} </tex>;<br/>
−
# <tex> \forall x \notin L \Rightarrow P(V^{P}(x) = 1) \le \frac{1}{3} </tex>;<br/>
+
# <tex> \forall x \notin L \Rightarrow P(\mathit{Verifier^{Prover}}(x) = 1) \le \frac{1}{3} </tex>;<br/>
 
# число раундов интерактивного протокола <tex> O(f(n)), n = |x|\} </tex>.<br/>
 
# число раундов интерактивного протокола <tex> O(f(n)), n = |x|\} </tex>.<br/>
 
}}
 
}}
Строка 45: Строка 45:
 
{{Определение
 
{{Определение
 
|definition =
 
|definition =
−
Если для интерактивного протокола выполняется <tex> \forall x \in L \Rightarrow P(V^{P}(x) = 1) = 1 </tex>, то говорят, что он обладает свойством <b> completeness </b>.
+
Если для интерактивного протокола выполняется <tex> \forall x \in L \Rightarrow P(\mathit{Verifier^{Prover}}(x) = 1) = 1 </tex>, то говорят, что он обладает свойством <b> completeness </b>.
 
}}
 
}}
  
 
{{Определение
 
{{Определение
 
|definition =
 
|definition =
−
Если для интерактивного протокола выполняется <tex> \forall x \notin L \Rightarrow P(V^{P}(x) = 1) = 0 </tex>, то говорят, что он обладает свойством <b> soundness </b>.
+
Если для интерактивного протокола выполняется <tex> \forall x \notin L \Rightarrow P(\mathit{Verifier^{Prover}}(x) = 1) = 0 </tex>, то говорят, что он обладает свойством <b> soundness </b>.
 
}}  
 
}}  
 
Свойство completeness можно достичь, а soundness достичь нельзя.
 
Свойство completeness можно достичь, а soundness достичь нельзя.
−
 
−
== Соотношения с другими классами теории сложности ==
 
−
 
−
{{Теорема
 
−
|statement=<tex>\mathrm{BPP} \subset \mathrm{IP}[0]</tex>.
 
−
|proof=
 
−
<tex>V</tex> сам по себе является вероятностной машиной Тьюринга и поэтому может разрешить язык из <tex>\mathrm{BPP}</tex> не прибегая к общению с <tex>P</tex>.
 
−
}}
 
−
 
−
{{Теорема
 
−
|statement=<tex>\mathrm{NP} \subset \mathrm{IP}[1]</tex>.
 
−
|proof=
 
−
Для разрешения языка из <tex>\mathrm{NP}</tex> будем использовать следующий протокол:
 
−
<tex>V</tex> будет проверять на принадлежность слова <tex>x</tex> используя сертификат, который он запросит у <tex>P</tex>. Так как <tex>P</tex> не ограничен в вычислительной мощности, он может подобрать подходящий сертификат и именно его и сообщит, так как он заинтересован в том, чтобы <tex>V</tex> принял слово. Для этого требуется лишь один раунд интерактивного протокола.
 
−
}}
 
−
 
−
== Язык GNI ==
 
−
{{Определение
 
−
|definition=
 
−
<tex>\mathrm{GNI}</tex> расшифровывается как Graph Non Isomorphism. Это язык пар неизоморфных друг другу графов.
 
−
<tex>\mathrm{GNI}=\{ \langle G, H \rangle, </tex> графы <tex>G</tex> и <tex>H</tex> не изоморфны <tex>\}</tex>.
 
−
}}
 
−
 
−
{{Теорема
 
−
|statement=<tex>\mathrm{GNI} \in \mathrm{IP}[1]</tex>.
 
−
|proof=
 
−
Будем использовать следующий алгоритм для <tex>V</tex>:
 
−
# Возьмём случайное число <tex>i \in \{0, 1\}</tex> и случайную перестановку <tex>\pi</tex> с вероятностной ленты; <br/>
 
−
# Создадим новый граф, перемешав вершины графа c номером <tex>i</tex> перестановкой <tex>\pi</tex>; <br/>
 
−
# Перешлём <tex>P</tex> полученный граф с просьбой определить, из какого из исходных графов он был получен; <br/>
 
−
# Получив ответ, сравним его с правильным ответом — числом <tex>i</tex>; <br/>
 
−
# Если полученный ответ не совпадёт с <tex>i</tex>, то вернём <tex>0</tex>; <br/>
 
−
# Иначе повторим первые пять шагов ещё раз и перейдём к последнему шагу; <br/>
 
−
# Если мы ещё не вернули <tex>0</tex>, то вернём <tex>1</tex>.
 
−
 
−
Покажем, что это удовлетворяет ограничениям на <tex>\mathrm{IP}[1]</tex>.
 
−
Во-первых, очевидно, что число раундов не превосходит двух. <br/>
 
−
Рассмотрим теперь случаи
 
−
* <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 \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>.
 
−
Таким образом, построенный протокол удовлетворяет условию теоремы.
 
−
}}
 
−
 
−
== См. также ==
 
−
*[[Вероятностные вычисления. Вероятностная машина Тьюринга]]
 
−
*[[Классы NP и Σ₁]]
 
−
 
−
[[Категория: Теория сложности]]
 

Версия 01:07, 5 июня 2012

Определения

Определение:
Интерактивным протоколом, разрешающим язык [math]L[/math], называется абстрактная машина (см. рисунок), моделирующая вычисления как обмен сообщениями между двумя программами ([math]\mathit{Prover}[/math] и [math]\mathit{Verifier}[/math]), такими, что
  1. [math]\mathit{Prover}[/math] заинтересован в том, чтобы [math]\mathit{Verifier}[/math] решил, что слово [math]x[/math] принадлежит языку;
  2. [math]\mathit{Prover}[/math] не ограничен в вычислительной мощности;
  3. [math]\mathit{Verifier}[/math] заинтересован установить, действительно ли слово [math]x[/math] принадлежит языку;
  4. [math]\mathit{Verifier}[/math] — вероятностная машина Тьюринга;
  5. [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]
  1. [math]\mathit{Prover}[/math] не имеет доступа к вероятностной ленте [math]\mathit{Verifier}[/math] (private coins);
  2. [math] \forall x \in L \Rightarrow P(\mathit{Verifier^{Prover}}(x) = 1) \ge \frac{2}{3} [/math];
  3. [math] \forall x \notin L \Rightarrow P(\mathit{Verifier^{Prover}}(x) = 1) \le \frac{1}{3} [/math];
  4. число раундов интерактивного протокола [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]
  1. [math]\mathit{Prover}[/math] может читать вероятностную ленту [math]\mathit{Verifier}[/math] (public coins);
  2. [math] \forall x \in L \Rightarrow P(\mathit{Verifier^{Prover}}(x) = 1) \ge \frac{2}{3} [/math];
  3. [math] \forall x \notin L \Rightarrow P(\mathit{Verifier^{Prover}}(x) = 1) \le \frac{1}{3} [/math];
  4. число раундов интерактивного протокола [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 достичь нельзя.

Источник — «http://neerc.ifmo.ru/wiki/index.php?title=Интерактивные_протоколы._Класс_IP._Класс_AM&oldid=23980»