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

Материал из Викиконспекты
Перейти к: навигация, поиск
(См. также)
м (rollbackEdits.php mass rollback)
 
(не показаны 24 промежуточные версии 6 участников)
Строка 1: Строка 1:
==Класс IP==
+
== Определения ==
  
 
{{Определение
 
{{Определение
 
|definition =
 
|definition =
<b>Интерактивным протоколом</b>, разрешающим язык <tex>L</tex>, называется абстрактная машина (см. рис. 1), моделирующая вычисления как обмен сообщениями между двумя программами (Prover и Verifier, далее <tex>P</tex> и <tex>V</tex> соответственно), такими, что
+
<b>Интерактивным протоколом</b> (англ. ''interactive protocol'') <tex> \langle P, V \rangle </tex>, разрешающим язык <tex>L</tex>, называется абстрактная машина (см. рисунок), моделирующая вычисления как обмен сообщениями между двумя программами (где <tex>P</tex> означает <tex> \mathrm{Prover}</tex> и <tex> V </tex> означает <tex>\mathrm{Verifier}</tex>), такими, что
# <tex>P</tex> заинтересован в том, чтобы <tex>V</tex> решил, что слово <tex>x</tex> принадлежит языку;
+
# <tex>P</tex> заинтересован в том, чтобы <tex>V</tex> решил, что слово <tex>x</tex> принадлежит языку.
# <tex>P</tex> не ограничен в вычислительной мощности;
+
# <tex>P</tex> не ограничен по времени вычисления и памяти.
# <tex>V</tex> заинтересован установить, действительно ли слово <tex>x</tex> принадлежит языку;
+
# <tex>V</tex> заинтересован установить, действительно ли слово <tex>x</tex> принадлежит языку.
# <tex>V</tex> [[Вероятностные вычисления. Вероятностная машина Тьюринга|вероятностная машина Тьюринга]];
+
# <tex>V</tex> {{---}} [[Вероятностные вычисления. Вероятностная машина Тьюринга|вероятностная машина Тьюринга]].
 
# <tex>V</tex> ограничен полиномиальным временем работы.
 
# <tex>V</tex> ограничен полиномиальным временем работы.
 
}}
 
}}
 +
[[Файл:IPS.png|600px|thumb|right|Схема интерактивного протокола.]]
  
<tex>V</tex>, обменивающийся сообщениями с <tex>P</tex>, будем обозначать <tex>V^{P}</tex>.
+
'''Замечания''':
 
+
# <tex> V </tex> и <tex> P </tex> по очереди становятся активными. <tex> V </tex> активизируется первым. В течение работы <tex> V </tex> выполняет вычисления, используя вход, очередные данные с вероятностной ленты и сообщение, пришедшее от <tex> P </tex>, и пишет запрос <tex> P </tex>. Как только <tex> V </tex> написал сообщение, он дизактивируется, и <tex> P </tex> становится активным, если протокол не завершился. Любая машина может завершить выполнение протокола просто не посылая сообщение во время своей активной фазы. <tex> V </tex> принимает (или отвергает) вход, выводит '''true''' (или '''false''') и завершает выполнение протокола. Время работы <tex> V </tex> {{---}} это сумма времен работы, затраченных <tex> V </tex> в течение активной фазы, и это время ограничено полиномом от длины входа.
[[Файл:IPS.png|250px|thumb|right|Рис. 1. Схема интерактивного протокола.]]
+
# <tex>V</tex>, обменивающийся сообщениями с фиксированным <tex>P</tex>, обозначим <tex>V_{P}</tex>.
 +
# Для того, чтобы <tex> V </tex> принял слово, <tex>P</tex> старается максимизировать вероятность <tex>\mathbb{P}(V_{P}(x) = 1)</tex>, выбирая нужные ответы на запросы.
 +
# Так как мы не ограничиваем <tex>P</tex> в вычислительной мощности, то он может работать бесконечное время, а значит <tex>V</tex> не получит ответ на какой-то вопрос. Но <tex>P</tex> хочет, чтобы <tex> V</tex> принял слово, значит нужно выбирать "хорошие" протоколы, чтобы таких ситуаций не появлялось.
 +
# <tex> P </tex> может быть и вероятностной и детерминированной машиной Тьюринга. Так как он имеет неограниченные вычислительные ресурсы, то на каждом ходу он может выбрать такие вероятностные данные и произвести вычисления с ними, что они максимизируют вероятность принятия слова <tex> V </tex>.
 +
# С другой стороны, для <tex> V </tex> важно быть вероятностной программой, так как иначе он будет принимать или отвергать слова с вероятностью <tex> 1 </tex>. И пользуясь предыдущим фактом, получим, что <tex> V_{P} </tex> всегда принимает слова из <tex> L </tex>.  
 +
# Так как <tex> V </tex> может писать и читать полиномиальное число символов, то длина сообщений между <tex> V </tex> и <tex> P </tex> есть полином от длины <tex> x </tex>.  
  
 
Интерактивные протоколы делятся на два типа в зависимости от доступа <tex>P</tex> к вероятностной ленте <tex>V</tex>:
 
Интерактивные протоколы делятся на два типа в зависимости от доступа <tex>P</tex> к вероятностной ленте <tex>V</tex>:
# <b> public coins </b> — <tex>P</tex> может видеть вероятностную ленту <tex>V</tex>;
+
# ''' public coins ''' (русск. ''открытые монеты'') {{---}} <tex>P</tex> может видеть вероятностную ленту <tex>V</tex>;
# <b> private coins </b> — <tex>P</tex> <b>не</b> может видеть вероятностную ленту <tex>V</tex>.
+
# ''' private coins ''' (русск. ''закрытые монеты''){{---}} <tex>P</tex> <b>не</b> может видеть вероятностную ленту <tex>V</tex>.
  
 
{{Определение
 
{{Определение
 
|definition =
 
|definition =
<tex>\mathrm{IP}[f] = \{L\bigm|\exists \langle V, P \rangle : </tex> <br/>
+
Если для интерактивного протокола выполняется <tex> \forall x \in L \Rightarrow  \exists P : \mathbb{P}(V_{P}(x) = 1) \geqslant c </tex>, то говорят, что он обладает свойством ''' completeness ''' (русск. ''полнота'') равным <tex> c </tex>.
# <tex>P</tex> не имеет доступа к вероятностной ленте <tex>V</tex> (private coins);
 
# <tex> \forall x \in L \Rightarrow P(V^{P}(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> O(f(n)), n = |x|\}</tex>.<br/>
 
 
}}
 
}}
 +
Если <tex>c = 1</tex> ('''perfect completeness''' (русск. ''идеальная полнота'')), то это означает, что никакое верное утверждение не отклоняется <tex> V </tex>.
  
Язык <tex>\mathrm{AM}</tex> (<i>Arthur–Merlin games</i>) отличается от <tex>\mathrm{IP}</tex> лишь тем, что <tex>P</tex> может видеть вероятностную ленту <tex>V</tex>.
 
 
{{Определение
 
{{Определение
 
|definition =
 
|definition =
<tex>\mathrm{AM}[f] = \{L\bigm|\exists \langle V, P \rangle : </tex> <br/>
+
Если для интерактивного протокола выполняется <tex> \forall x \notin L \Rightarrow \forall P : \mathbb{P}(V_{P}(x) = 1) \leqslant 1 - s </tex>, то говорят, что он обладает свойством ''' soundness ''' (русск. ''достоверность'') равным <tex> s </tex>.
# <tex>P</tex> может читать вероятностную ленту <tex>V</tex> (public coins);
+
}}
# <tex> \forall x \in L \Rightarrow P(V^{P}(x) = 1) \ge \frac{2}{3} </tex>;<br/>
+
Если <tex>s = 1 </tex> ('''perfect soundness''' (русск. ''идеальная достоверность'')), то это означет, что если утверждение ложно, то никакой <tex>P</tex> не может убедить <tex>V</tex>, что утверждение истино. В этом случае мы получем класс <tex> \mathrm{NP} </tex>. Потому что <tex> x \in L </tex> тогда и только тогда, если существует последовательность случайных вопросов, генерируемых <tex> V </tex>, и последовательность ответов <tex> P </tex>, которые убеждают <tex> V </tex> в том, что <tex> x \in L </tex>. Обратное утверждение сохраняется по предположению идеальной достоверности.
# <tex> \forall x \notin L \Rightarrow P(V^{P}(x) = 1) \le \frac{1}{3} </tex>;<br/>
 
# число раундов интерактивного протокола <tex> O(f(n)), n = |x|\} </tex>.<br/>
 
}}
 
  
 
{{Определение
 
{{Определение
|definition = <tex>\mathrm{IP}=\bigcup\limits_{p(n) \in poly} \mathrm{IP} [p(n)] </tex>
+
|definition =
 +
<tex>\mathrm{IP}[f] </tex> (''Interactive Polynomial time'') <tex> = \{L \mid \exists </tex> интерактивный протокол <tex>\langle P, V \rangle : </tex>
 +
# <tex>P</tex> не имеет доступа к вероятностной ленте <tex>V</tex> (private coins).
 +
# <tex> c \geqslant 2/{3} </tex>.
 +
# <tex> s \geqslant 2 /{3} </tex>.
 +
# число раундов интерактивного протокола <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> {{---}} множество языков разрешимых интерактивным протоколом, таких, что число сообщений ограничено полиномом от длины слова и <tex>V</tex> должен решить лежит ли слово в языке с вероятностью ошибки не более <tex>1/{3}</tex>.
  
 +
Язык <tex>\mathrm{AM}</tex> (''Arthur–Merlin games'') отличается от <tex>\mathrm{IP}</tex> лишь тем, что <tex>P</tex> может видеть вероятностную ленту <tex>V</tex>.
 
{{Определение
 
{{Определение
 
|definition =
 
|definition =
Если для интерактивного протокола выполняется <tex> \forall x \in L \Rightarrow P(V^{P}(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).
 +
# <tex> c \geqslant 2/{3} </tex>.
 +
# <tex> s \geqslant 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(V^{P}(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>V</tex> сам по себе является вероятностной машиной Тьюринга и поэтому может разрешить язык из <tex>\mathrm{BPP}</tex> не прибегая к общению с <tex>P</tex>.
+
<tex>V</tex> сам по себе является вероятностной машиной Тьюринга и поэтому может разрешить [[Классы_BPP_и_PP|язык из <tex>\mathrm{BPP}</tex>]] не прибегая к общению с <tex>P</tex>.
 
}}
 
}}
  
Строка 67: Строка 75:
 
|statement=<tex>\mathrm{NP} \subset \mathrm{IP}[1]</tex>.
 
|statement=<tex>\mathrm{NP} \subset \mathrm{IP}[1]</tex>.
 
|proof=
 
|proof=
Для разрешения языка из <tex>\mathrm{NP}</tex> будем использовать следующий протокол:
+
Для разрешения [[Классы_NP_и_Σ₁#.D0.9E.D0.BF.D1.80.D0.B5.D0.B4.D0.B5.D0.BB.D0.B5.D0.BD.D0.B8.D1.8F.2C_.D1.81.D0.B2.D1.8F.D0.B7.D1.8C_.CE.A3.E2.82.81_.D0.B8_NP|языка из <tex>\mathrm{NP}</tex>]] будем использовать следующий протокол:
<tex>V</tex> будет проверять на принадлежность слова <tex>x</tex> используя сертификат, который он запросит у <tex>P</tex>. Так как <tex>P</tex> не ограничен в вычислительной мощности, он может подобрать подходящий сертификат и именно его и сообщит, так как он заинтересован в том, чтобы <tex>V</tex> принял слово. Для этого требуется лишь один раунд интерактивного протокола.
+
<tex>V</tex> будет проверять на принадлежность слова <tex>x</tex> языку, используя сертификат, который он запросит у <tex>P</tex>. Так как <tex>P</tex> не ограничен в вычислительной мощности, он может подобрать подходящий сертификат и именно его и сообщит, так как он заинтересован в том, чтобы <tex>V</tex> принял слово. Для этого требуется лишь один раунд интерактивного протокола.
 
}}
 
}}
  
 +
== Язык GNI ==
 
{{Определение
 
{{Определение
 
|definition=
 
|definition=
<tex>\mathrm{GNI}</tex> расшифровывается как Graph Non Isomorphism. Это язык пар неизоморфных друг другу графов.
+
<tex>\mathrm{GNI}</tex> расшифровывается как Graph Non Isomorphism. Это язык пар [[Основные_определения_теории_графов#.D0.9E.D1.80.D0.B8.D0.B5.D0.BD.D1.82.D0.B8.D1.80.D0.BE.D0.B2.D0.B0.D0.BD.D0.BD.D1.8B.D0.B5_.D0.B3.D1.80.D0.B0.D1.84.D1.8B|неизоморфных друг другу графов]].
<tex>\mathrm{GNI}=\{ \langle G, H \rangle, </tex> графы <tex>G</tex> и <tex>H</tex> не изоморфны <tex>\}</tex>.
+
<tex>\mathrm{GNI}=\{ \langle G, H \rangle \mid </tex> графы <tex>G</tex> и <tex>H</tex> не изоморфны <tex>\}</tex>.
 
}}
 
}}
  
Строка 80: Строка 89:
 
|statement=<tex>\mathrm{GNI} \in \mathrm{IP}[1]</tex>.
 
|statement=<tex>\mathrm{GNI} \in \mathrm{IP}[1]</tex>.
 
|proof=
 
|proof=
 +
Пусть на вход подали пару графов <tex> \langle G_{0}, G_{1} \rangle </tex> и нужно определить изоморфны ли они.
 
Будем использовать следующий алгоритм для <tex>V</tex>:
 
Будем использовать следующий алгоритм для <tex>V</tex>:
# Возьмём случайное число <tex>i \in \{0, 1\}</tex> и случайную перестановку <tex>\pi</tex> с вероятностной ленты; <br/>
+
# Возьмём случайное число <tex>i \in \{0, 1\}</tex> и [[Комбинаторные_объекты|случайную перестановку]] <tex>\pi</tex> с вероятностной ленты;
# Создадим новый граф, перемешав вершины графа c номером <tex>i</tex> перестановкой <tex>\pi</tex>; <br/>
+
# Создадим новый граф <tex> G </tex>, перемешав вершины графа c номером <tex>i</tex> перестановкой <tex>\pi</tex>.
# Перешлём <tex>P</tex> полученный граф с просьбой определить, из какого из исходных графов он был получен; <br/>
+
# Перешлём <tex>P</tex> полученный граф <tex> G </tex> с просьбой определить, из какого из исходных графов он был получен. Если <tex>G_{0} \ncong G_{1} </tex>, то он может перебрать все перестановки графов <tex> G_{0}, G_{1} </tex>, и так как <tex>G_{0} \ncong G_{1} </tex>, то только одна перестановка только на одном графе даст <tex> G </tex>. Иначе, существуют такие перестановки <tex> \phi, \psi </tex>, что <tex> \phi(G_0) = \psi(G_1) = G </tex>, и <tex> P </tex> никак не сможет определить из какого графа был получен <tex> G </tex>. Тогда <tex> P </tex> просто попытается угадать граф, вернув случайно <tex> 0 </tex> или <tex> 1 </tex>.
# Получив ответ, сравним его с правильным ответом — числом <tex>i</tex>; <br/>
+
# Получив ответ, сравним его с правильным ответом — числом <tex>i</tex>.
# Если полученный ответ не совпадёт с <tex>i</tex>, то вернём <tex>0</tex>; <br/>
+
# Если полученный ответ не совпадёт с <tex>i</tex>, то вернём <tex>0</tex>.
# Иначе повторим первые пять шагов ещё раз и перейдём к последнему шагу; <br/>
+
# Иначе повторим первые пять шагов ещё раз и перейдём к последнему шагу.
 
# Если мы ещё не вернули <tex>0</tex>, то вернём <tex>1</tex>.
 
# Если мы ещё не вернули <tex>0</tex>, то вернём <tex>1</tex>.
  
 
Покажем, что это удовлетворяет ограничениям на <tex>\mathrm{IP}[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>.
+
* <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> вернёт <tex>1</tex>. То есть получили completeness равную <tex> 1 </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> 0.5 </tex>), равна <tex>0.25</tex>. Значит soundness равна <tex> 0.75 </tex>, что больше или равно <tex> 2/{3} </tex>.
 
Таким образом, построенный протокол удовлетворяет условию теоремы.
 
Таким образом, построенный протокол удовлетворяет условию теоремы.
 
}}
 
}}
Строка 100: Строка 111:
 
*[[Вероятностные вычисления. Вероятностная машина Тьюринга]]
 
*[[Вероятностные вычисления. Вероятностная машина Тьюринга]]
 
*[[Классы NP и Σ₁]]
 
*[[Классы NP и Σ₁]]
 +
*[[Классы BPP и PP]]
 +
 +
== Источники информации ==
 +
*[[wikipedia: Interactive_proof_system | Wikipedia {{---}} Interactive proof system]]
  
 
[[Категория: Теория сложности]]
 
[[Категория: Теория сложности]]
 +
[[Категория: Вероятностные сложностные классы]]
 +
[[Категория: Интерактивные протоколы]]

Текущая версия на 19:31, 4 сентября 2022

Определения

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

Замечания:

  1. [math] V [/math] и [math] P [/math] по очереди становятся активными. [math] V [/math] активизируется первым. В течение работы [math] V [/math] выполняет вычисления, используя вход, очередные данные с вероятностной ленты и сообщение, пришедшее от [math] P [/math], и пишет запрос [math] P [/math]. Как только [math] V [/math] написал сообщение, он дизактивируется, и [math] P [/math] становится активным, если протокол не завершился. Любая машина может завершить выполнение протокола просто не посылая сообщение во время своей активной фазы. [math] V [/math] принимает (или отвергает) вход, выводит true (или false) и завершает выполнение протокола. Время работы [math] V [/math] — это сумма времен работы, затраченных [math] V [/math] в течение активной фазы, и это время ограничено полиномом от длины входа.
  2. [math]V[/math], обменивающийся сообщениями с фиксированным [math]P[/math], обозначим [math]V_{P}[/math].
  3. Для того, чтобы [math] V [/math] принял слово, [math]P[/math] старается максимизировать вероятность [math]\mathbb{P}(V_{P}(x) = 1)[/math], выбирая нужные ответы на запросы.
  4. Так как мы не ограничиваем [math]P[/math] в вычислительной мощности, то он может работать бесконечное время, а значит [math]V[/math] не получит ответ на какой-то вопрос. Но [math]P[/math] хочет, чтобы [math] V[/math] принял слово, значит нужно выбирать "хорошие" протоколы, чтобы таких ситуаций не появлялось.
  5. [math] P [/math] может быть и вероятностной и детерминированной машиной Тьюринга. Так как он имеет неограниченные вычислительные ресурсы, то на каждом ходу он может выбрать такие вероятностные данные и произвести вычисления с ними, что они максимизируют вероятность принятия слова [math] V [/math].
  6. С другой стороны, для [math] V [/math] важно быть вероятностной программой, так как иначе он будет принимать или отвергать слова с вероятностью [math] 1 [/math]. И пользуясь предыдущим фактом, получим, что [math] V_{P} [/math] всегда принимает слова из [math] L [/math].
  7. Так как [math] V [/math] может писать и читать полиномиальное число символов, то длина сообщений между [math] V [/math] и [math] P [/math] есть полином от длины [math] x [/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 c [/math], то говорят, что он обладает свойством completeness (русск. полнота) равным [math] c [/math].

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


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

Если [math]s = 1 [/math] (perfect soundness (русск. идеальная достоверность)), то это означет, что если утверждение ложно, то никакой [math]P[/math] не может убедить [math]V[/math], что утверждение истино. В этом случае мы получем класс [math] \mathrm{NP} [/math]. Потому что [math] x \in L [/math] тогда и только тогда, если существует последовательность случайных вопросов, генерируемых [math] V [/math], и последовательность ответов [math] P [/math], которые убеждают [math] V [/math] в том, что [math] x \in L [/math]. Обратное утверждение сохраняется по предположению идеальной достоверности.


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

Язык [math]\mathrm{AM}[/math] (Arthur–Merlin games) отличается от [math]\mathrm{IP}[/math] лишь тем, что [math]P[/math] может видеть вероятностную ленту [math]V[/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. [math] c \geqslant 2/{3} [/math].
  3. [math] s \geqslant 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]V[/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 \mid [/math] графы [math]G[/math] и [math]H[/math] не изоморфны [math]\}[/math].


Теорема:
[math]\mathrm{GNI} \in \mathrm{IP}[1][/math].
Доказательство:
[math]\triangleright[/math]

Пусть на вход подали пару графов [math] \langle G_{0}, G_{1} \rangle [/math] и нужно определить изоморфны ли они. Будем использовать следующий алгоритм для [math]V[/math]:

  1. Возьмём случайное число [math]i \in \{0, 1\}[/math] и случайную перестановку [math]\pi[/math] с вероятностной ленты;
  2. Создадим новый граф [math] G [/math], перемешав вершины графа c номером [math]i[/math] перестановкой [math]\pi[/math].
  3. Перешлём [math]P[/math] полученный граф [math] G [/math] с просьбой определить, из какого из исходных графов он был получен. Если [math]G_{0} \ncong G_{1} [/math], то он может перебрать все перестановки графов [math] G_{0}, G_{1} [/math], и так как [math]G_{0} \ncong G_{1} [/math], то только одна перестановка только на одном графе даст [math] G [/math]. Иначе, существуют такие перестановки [math] \phi, \psi [/math], что [math] \phi(G_0) = \psi(G_1) = G [/math], и [math] P [/math] никак не сможет определить из какого графа был получен [math] G [/math]. Тогда [math] P [/math] просто попытается угадать граф, вернув случайно [math] 0 [/math] или [math] 1 [/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] вернёт [math]1[/math]. То есть получили completeness равную [math] 1 [/math].
  • [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] 0.5 [/math]), равна [math]0.25[/math]. Значит soundness равна [math] 0.75 [/math], что больше или равно [math] 2/{3} [/math].
Таким образом, построенный протокол удовлетворяет условию теоремы.
[math]\triangleleft[/math]

См. также

Источники информации