211
правок
Изменения
Отмена правки 23980 участника Байдаров Андрей (обсуждение)
{{Определение
|definition =
<b>Интерактивным протоколом</b>, разрешающим язык <tex>L</tex>, называется абстрактная машина (см. рисунок), моделирующая вычисления как обмен сообщениями между двумя программами (Prover и Verifier, далее <tex>\mathit{Prover}P</tex> и <tex>\mathit{Verifier}V</tex>соответственно), такими, что# <tex>\mathit{Prover}P</tex> заинтересован в том, чтобы <tex>\mathit{Verifier}V</tex> решил, что слово <tex>x</tex> принадлежит языку;# <tex>\mathit{Prover}P</tex> не ограничен в вычислительной мощности;# <tex>\mathit{Verifier}V</tex> заинтересован установить, действительно ли слово <tex>x</tex> принадлежит языку;# <tex>\mathit{Verifier}V</tex> — [[Вероятностные вычисления. Вероятностная машина Тьюринга|вероятностная машина Тьюринга]];# <tex>\mathit{Verifier}V</tex> ограничен полиномиальным временем работы.
}}
[[Файл:IPS.png|250px|thumb|right|Схема интерактивного протокола.]]
<tex>\mathit{Verifier}V</tex>, обменивающийся сообщениями с <tex>\mathit{Prover}P</tex>, будем обозначать <tex>\mathit{VerifierV^{Prover}P}</tex>.
Интерактивные протоколы делятся на два типа в зависимости от доступа <tex>\mathit{Prover}P</tex> к вероятностной ленте <tex>\mathit{Verifier}V</tex>:# <b> public coins </b> — <tex>\mathit{Prover}P</tex> может видеть вероятностную ленту <tex>\mathit{Verifier}V</tex>;# <b> private coins </b> — <tex>\mathit{Prover}P</tex> <b>не</b> может видеть вероятностную ленту <tex>\mathit{Verifier}V</tex>.
{{Определение
|definition =
<tex>\mathrm{IP}[f] = \{L\bigm|\exists \langle \mathit{Verifier}V, \mathit{Prover} P \rangle : </tex> <br/># <tex>\mathit{Prover}P</tex> не имеет доступа к вероятностной ленте <tex>\mathit{Verifier}V</tex> (private coins);# <tex> \forall x \in L \Rightarrow P(\mathit{VerifierV^{Prover}P}(x) = 1) \ge \frac{2}{3} </tex>;<br/># <tex> \forall x \notin L \Rightarrow P(\mathit{VerifierV^{Prover}P}(x) = 1) \le \frac{1}{3} </tex>;<br/>
# число раундов интерактивного протокола <tex> O(f(n)), n = |x|\}</tex>.<br/>
}}
}}
Язык <tex>\mathrm{AM}</tex> (<i>Arthur–Merlin games</i>) отличается от <tex>\mathrm{IP}</tex> лишь тем, что <tex>\mathit{Prover}P</tex> может видеть вероятностную ленту <tex>\mathit{Verifier}V</tex>.
{{Определение
|definition =
<tex>\mathrm{AM}[f] = \{L\bigm|\exists \langle \mathit{Verifier}V, \mathit{Prover} P \rangle : </tex> <br/># <tex>\mathit{Prover}P</tex> может читать вероятностную ленту <tex>\mathit{Verifier}V</tex> (public coins);# <tex> \forall x \in L \Rightarrow P(\mathit{VerifierV^{Prover}P}(x) = 1) \ge \frac{2}{3} </tex>;<br/># <tex> \forall x \notin L \Rightarrow P(\mathit{VerifierV^{Prover}P}(x) = 1) \le \frac{1}{3} </tex>;<br/>
# число раундов интерактивного протокола <tex> O(f(n)), n = |x|\} </tex>.<br/>
}}
{{Определение
|definition =
Если для интерактивного протокола выполняется <tex> \forall x \in L \Rightarrow P(\mathit{VerifierV^{Prover}P}(x) = 1) = 1 </tex>, то говорят, что он обладает свойством <b> completeness </b>.
}}
{{Определение
|definition =
Если для интерактивного протокола выполняется <tex> \forall x \notin L \Rightarrow P(\mathit{VerifierV^{Prover}P}(x) = 1) = 0 </tex>, то говорят, что он обладает свойством <b> soundness </b>.
}}
Свойство 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 и Σ₁]]
[[Категория: Теория сложности]]
