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

Материал из Викиконспекты
Перейти к: навигация, поиск
м
Строка 3: Строка 3:
 
{{Определение
 
{{Определение
 
|definition =
 
|definition =
<b>Интерактивным протоколом</b>, разрешающим язык <tex>L</tex>, называется абстрактная машина (см. рисунок), моделирующая вычисления как обмен сообщениями между двумя программами (<tex>\mathit{Prover}</tex> и <tex>\mathit{Verifier}</tex>), такими, что
+
<b>Интерактивным протоколом</b> <tex> \langle P, V \rangle </tex>, разрешающим язык <tex>L</tex>, называется абстрактная машина (см. рисунок) , моделирующая вычисления как обмен сообщениями между двумя программами (где <tex>P</tex> означает <tex> \mathit{Prover}</tex> и <tex> V </tex> означает <tex>\mathit{Verifier}</tex>), такими, что
# <tex>\mathit{Prover}</tex> заинтересован в том, чтобы <tex>\mathit{Verifier}</tex> решил, что слово <tex>x</tex> принадлежит языку;
+
# <tex>P</tex> заинтересован в том, чтобы <tex>V</tex> решил, что слово <tex>x</tex> принадлежит языку;
# <tex>\mathit{Prover}</tex> не ограничен в вычислительной мощности;
+
# <tex>P</tex> не ограничен по времени вычисления и памяти;
# <tex>\mathit{Verifier}</tex> заинтересован установить, действительно ли слово <tex>x</tex> принадлежит языку;
+
# <tex>V</tex> заинтересован установить, действительно ли слово <tex>x</tex> принадлежит языку;
# <tex>\mathit{Verifier}</tex> [[Вероятностные вычисления. Вероятностная машина Тьюринга|вероятностная машина Тьюринга]];
+
# <tex>V</tex> {{---}} [[Вероятностные вычисления. Вероятностная машина Тьюринга|вероятностная машина Тьюринга]];
# <tex>\mathit{Verifier}</tex> ограничен полиномиальным временем работы.
+
# <tex>V</tex> ограничен полиномиальным временем работы.
 
}}
 
}}
 
[[Файл:IPS.png|600px|thumb|right|Схема интерактивного протокола.]]
 
[[Файл:IPS.png|600px|thumb|right|Схема интерактивного протокола.]]
  
<tex>\mathit{Verifier}</tex>, обменивающийся сообщениями с <tex>\mathit{Prover}</tex>, будем обозначать <tex>\mathit{Verifier^{Prover}}</tex>.
+
<tex>V</tex>, обменивающийся сообщениями с <tex>P</tex>, обозначим <tex>V_{P}</tex>.
  
Интерактивные протоколы делятся на два типа в зависимости от доступа <tex>\mathit{Prover}</tex> к вероятностной ленте <tex>\mathit{Verifier}</tex>:
+
Интерактивные протоколы делятся на два типа в зависимости от доступа <tex>P</tex> к вероятностной ленте <tex>V</tex>:
# <b> public coins </b> — <tex>\mathit{Prover}</tex> может видеть вероятностную ленту <tex>\mathit{Verifier}</tex>;
+
# ''' public coins ''' {{---}} <tex>P</tex> может видеть вероятностную ленту <tex>V</tex>;
# <b> private coins </b> — <tex>\mathit{Prover}</tex> <b>не</b> может видеть вероятностную ленту <tex>\mathit{Verifier}</tex>.
+
# ''' private coins ''' {{---}} <tex>P</tex> <b>не</b> может видеть вероятностную ленту <tex>V</tex>.
  
 
{{Определение
 
{{Определение
 
|definition =
 
|definition =
<tex>\mathrm{IP}[f] = \{L\bigm|\exists \langle \mathit{Verifier}, \mathit{Prover} \rangle : </tex> <br/>
+
Если для интерактивного протокола выполняется <tex> \forall x \in L \Rightarrow \exists P : \mathbb{P}(V_{P}(x) = 1) \geqslant \alpha </tex>, то говорят, что он обладает свойством ''' completeness ''' равным <tex> \alpha </tex>.
# <tex>\mathit{Prover}</tex> не имеет доступа к вероятностной ленте <tex>\mathit{Verifier}</tex> (private coins);
 
# <tex> \forall x \in L \Rightarrow P(\mathit{Verifier^{Prover}}(x) = 1) \geqslant \frac{2}{3} </tex>;<br/>
 
# <tex> \forall x \notin L \Rightarrow P(\mathit{Verifier^{Prover}}(x) = 1) \leqslant \frac{1}{3} </tex>;<br/>
 
# число раундов интерактивного протокола <tex> O(f(n)), n = |x|\}</tex>.<br/>
 
 
}}
 
}}
 +
Если completeness равно <tex>1</tex>, это означает, что никакое верное утверждение не отклоняется <tex> V </tex>.
 +
 
{{Определение
 
{{Определение
|definition = <tex>\mathrm{IP}=\bigcup\limits_{p(n) \in poly} \mathrm{IP} [p(n)] </tex>
+
|definition =
}}
+
Если для интерактивного протокола выполняется <tex> \forall x \notin L \Rightarrow \forall P : \mathbb{P}(V_{P}(x) = 1) \leqslant 1 - \alpha </tex>, то говорят, что он обладает свойством ''' soundness ''' равным <tex> \alpha </tex>.
 +
}}  
 +
Если soundeness равно <tex> 1 </tex>, это означет, что если утверждение ложно, то никакой <tex>P</tex> не может убедить <tex>V</tex>, что утверждение истино.
 +
 
 +
Свойство completeness можно достичь, а soundness достичь нельзя.
 +
 
  
Язык <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 \mathit{Verifier}, \mathit{Prover} \rangle : </tex> <br/>
+
<tex>\mathrm{IP}[f] = \{L \mid \exists </tex> интерактивный протокол <tex>\langle P, V \rangle : </tex>
# <tex>\mathit{Prover}</tex> может читать вероятностную ленту <tex>\mathit{Verifier}</tex> (public coins);
+
# <tex>P</tex> не имеет доступа к вероятностной ленте <tex>V</tex> (private coins);
# <tex> \forall x \in L \Rightarrow P(\mathit{Verifier^{Prover}}(x) = 1) \geqslant \frac{2}{3} </tex>;<br/>
+
# completeness равно <tex> 2/{3} </tex>;
# <tex> \forall x \notin L \Rightarrow P(\mathit{Verifier^{Prover}}(x) = 1) \leqslant \frac{1}{3} </tex>;<br/>
+
# soundeness равно <tex> 2 /{3} </tex>;
# число раундов интерактивного протокола <tex> O(f(n)), n = |x|\} </tex>.<br/>
+
# число раундов интерактивного протокола <tex> O(f(n)), n = |x|\}</tex>.
 
}}
 
}}
 
{{Определение
 
{{Определение
|definition = <tex>\mathrm{AM}=\bigcup\limits_{p(n) \in poly} \mathrm{AM} [p(n)] </tex>
+
|definition = <tex>\mathrm{IP}=\bigcup\limits_{p(n) \in poly} \mathrm{IP} [p(n)] </tex>
 
}}
 
}}
 +
То есть <tex> \mathrm{IP}</tex> (''Interactive Polynomial time'') {{---}} множество языков разрешимых интерактивным протоколом , таких, что число сообщений ограничено полиномом от длины слова и <tex>V</tex> должен решить лежит ли слово в языке с вероятностью ошибки не более <tex>1/{3}</tex>.
  
 +
Язык <tex>\mathrm{AM}</tex> (''Arthur–Merlin games'') отличается от <tex>\mathrm{IP}</tex> лишь тем, что <tex>\mathit{Prover}</tex> может видеть вероятностную ленту <tex>\mathit{Verifier}</tex>.
 
{{Определение
 
{{Определение
 
|definition =
 
|definition =
Если для интерактивного протокола выполняется <tex> \forall x \in L \Rightarrow P(\mathit{Verifier^{Prover}}(x) = 1) = 1 </tex>, то говорят, что он обладает свойством <b> completeness </b>.
+
<tex>\mathrm{AM}[f] = \{L \mid \exists </tex> интерактивный протокол <tex>\langle P, V \rangle : </tex>
 +
# <tex>P</tex> может читать вероятностную ленту <tex>V</tex> (public coins);
 +
# completeness равно <tex> 2/{3} </tex>;
 +
# soundeness равно <tex> 2 /{3} </tex>;
 +
# число раундов интерактивного протокола <tex> O(f(n)), n = |x|\}</tex>.
 
}}
 
}}
  
 
{{Определение
 
{{Определение
|definition =
+
|definition = <tex>\mathrm{AM}=\bigcup\limits_{p(n) \in poly} \mathrm{AM} [p(n)] </tex>
Если для интерактивного протокола выполняется <tex> \forall x \notin L \Rightarrow P(\mathit{Verifier^{Prover}}(x) = 1) = 0 </tex>, то говорят, что он обладает свойством <b> soundness </b>.
+
}}
}}  
 
Свойство completeness можно достичь, а soundness достичь нельзя.
 
  
 
== Соотношения с другими классами теории сложности ==
 
== Соотношения с другими классами теории сложности ==
  
 
{{Теорема
 
{{Теорема
|statement=<tex>\mathrm{BPP} \subset \mathrm{IP}[0]</tex>.
+
|statement=<tex>\mathrm{BPP}</tex> <tex>\subset \mathrm{IP}[0]</tex>.
 
|proof=
 
|proof=
<tex>\mathit{Verifier}</tex> сам по себе является вероятностной машиной Тьюринга и поэтому может разрешить язык из <tex>\mathrm{BPP}</tex> не прибегая к общению с <tex>\mathit{Prover}</tex>.
+
<tex>V</tex> сам по себе является вероятностной машиной Тьюринга и поэтому может разрешить [[Классы_BPP_и_PP|язык из <tex>\mathrm{BPP}</tex>]] не прибегая к общению с <tex>P</tex>.
 
}}
 
}}
  
Строка 66: Строка 72:
 
|proof=
 
|proof=
 
Для разрешения языка из <tex>\mathrm{NP}</tex> будем использовать следующий протокол:
 
Для разрешения языка из <tex>\mathrm{NP}</tex> будем использовать следующий протокол:
<tex>\mathit{Verifier}</tex> будет проверять на принадлежность слова <tex>x</tex> используя сертификат, который он запросит у <tex>\mathit{Prover}</tex>. Так как <tex>\mathit{Prover}</tex> не ограничен в вычислительной мощности, он может подобрать подходящий сертификат и именно его и сообщит, так как он заинтересован в том, чтобы <tex>\mathit{Verifier}</tex> принял слово. Для этого требуется лишь один раунд интерактивного протокола.
+
<tex>P</tex> будет проверять на принадлежность слова <tex>x</tex> языку, используя сертификат, который он запросит у <tex>P</tex>. Так как <tex>P</tex> не ограничен в вычислительной мощности, он может подобрать подходящий сертификат и именно его и сообщит, так как он заинтересован в том, чтобы <tex>V</tex> принял слово. Для этого требуется лишь один раунд интерактивного протокола.
 
}}
 
}}
  
Строка 99: Строка 105:
 
*[[Вероятностные вычисления. Вероятностная машина Тьюринга]]
 
*[[Вероятностные вычисления. Вероятностная машина Тьюринга]]
 
*[[Классы NP и Σ₁]]
 
*[[Классы NP и Σ₁]]
 +
*[[Классы BPP и PP]]
  
 
[[Категория: Теория сложности]]
 
[[Категория: Теория сложности]]

Версия 15:55, 30 апреля 2016

Определения

Определение:
Интерактивным протоколом [math] \langle P, V \rangle [/math], разрешающим язык [math]L[/math], называется абстрактная машина (см. рисунок) , моделирующая вычисления как обмен сообщениями между двумя программами (где [math]P[/math] означает [math] \mathit{Prover}[/math] и [math] V [/math] означает [math]\mathit{Verifier}[/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] ограничен полиномиальным временем работы.
Схема интерактивного протокола.

[math]V[/math], обменивающийся сообщениями с [math]P[/math], обозначим [math]V_{P}[/math].

Интерактивные протоколы делятся на два типа в зависимости от доступа [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] \forall x \in L \Rightarrow \exists P : \mathbb{P}(V_{P}(x) = 1) \geqslant \alpha [/math], то говорят, что он обладает свойством completeness равным [math] \alpha [/math].

Если completeness равно [math]1[/math], это означает, что никакое верное утверждение не отклоняется [math] V [/math].


Определение:
Если для интерактивного протокола выполняется [math] \forall x \notin L \Rightarrow \forall P : \mathbb{P}(V_{P}(x) = 1) \leqslant 1 - \alpha [/math], то говорят, что он обладает свойством soundness равным [math] \alpha [/math].

Если soundeness равно [math] 1 [/math], это означет, что если утверждение ложно, то никакой [math]P[/math] не может убедить [math]V[/math], что утверждение истино.

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


Определение:
[math]\mathrm{IP}[f] = \{L \mid \exists [/math] интерактивный протокол [math]\langle P, V \rangle : [/math]
  1. [math]P[/math] не имеет доступа к вероятностной ленте [math]V[/math] (private coins);
  2. completeness равно [math] 2/{3} [/math];
  3. soundeness равно [math] 2 /{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{IP}[/math] (Interactive Polynomial time) — множество языков разрешимых интерактивным протоколом , таких, что число сообщений ограничено полиномом от длины слова и [math]V[/math] должен решить лежит ли слово в языке с вероятностью ошибки не более [math]1/{3}[/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 \mid \exists [/math] интерактивный протокол [math]\langle P, V \rangle : [/math]
  1. [math]P[/math] может читать вероятностную ленту [math]V[/math] (public coins);
  2. completeness равно [math] 2/{3} [/math];
  3. soundeness равно [math] 2 /{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]\mathrm{BPP}[/math] [math]\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]P[/math] будет проверять на принадлежность слова [math]x[/math] языку, используя сертификат, который он запросит у [math]P[/math]. Так как [math]P[/math] не ограничен в вычислительной мощности, он может подобрать подходящий сертификат и именно его и сообщит, так как он заинтересован в том, чтобы [math]V[/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]:

  1. Возьмём случайное число [math]i \in \{0, 1\}[/math] и случайную перестановку [math]\pi[/math] с вероятностной ленты;
  2. Создадим новый граф, перемешав вершины графа c номером [math]i[/math] перестановкой [math]\pi[/math];
  3. Перешлём [math]\mathit{Prover}[/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]\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]

См. также