210
правок
Изменения
м
Нет описания правки
<tex>\mathrm{IP}[f] = \{L \mid \exists </tex> интерактивный протокол <tex>\langle P, V \rangle : </tex>
# <tex>P</tex> не имеет доступа к вероятностной ленте <tex>V</tex> (private coins);
# completeness равно <tex> \geqslant 2/{3} </tex>;# soundeness равно <tex> \geqslant 2 /{3} </tex>;
# число раундов интерактивного протокола <tex> O(f(n)), n = |x|\}</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}P</tex> может видеть вероятностную ленту <tex>\mathit{Verifier}V</tex>.
{{Определение
|definition =
<tex>\mathrm{AM}[f] = \{L \mid \exists </tex> интерактивный протокол <tex>\langle P, V \rangle : </tex>
# <tex>P</tex> может читать вероятностную ленту <tex>V</tex> (public coins);
# completeness равно <tex> \geqslant 2/{3} </tex>;# soundeness равно <tex> \geqslant 2 /{3} </tex>;
# число раундов интерактивного протокола <tex> O(f(n)), n = |x|\}</tex>.
}}
|statement=<tex>\mathrm{NP} \subset \mathrm{IP}[1]</tex>.
|proof=
Для разрешения [[Классы_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>P</tex> будет проверять на принадлежность слова <tex>x</tex> языку, используя сертификат, который он запросит у <tex>P</tex>. Так как <tex>P</tex> не ограничен в вычислительной мощности, он может подобрать подходящий сертификат и именно его и сообщит, так как он заинтересован в том, чтобы <tex>V</tex> принял слово. Для этого требуется лишь один раунд интерактивного протокола.
}}
{{Определение
|definition=
<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, \mid </tex> графы <tex>G</tex> и <tex>H</tex> не изоморфны <tex>\}</tex>.
}}
|statement=<tex>\mathrm{GNI} \in \mathrm{IP}[1]</tex>.
|proof=
Будем использовать следующий алгоритм для <tex>\mathit{Verifier}V</tex>:# Возьмём случайное число <tex>i \in \{0, 1\}</tex> и [[Комбинаторные_объекты|случайную перестановку ]] <tex>\pi</tex> с вероятностной ленты; <br/># Создадим новый граф, перемешав вершины графа c номером <tex>i</tex> перестановкой <tex>\pi</tex>; <br/># Перешлём <tex>\mathit{Prover}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>\mathit{Prover}P</tex> сможет определить какой граф был перемешан <tex>\mathit{Verifier}V</tex>. Таким образом, <tex>\mathit{Prover}P</tex> сможет два раза подряд вернуть правильный ответ и в итоге <tex>\mathit{Verifier}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>\mathit{Prover}P</tex> не сможет определить какой граф был перемешан <tex>\mathit{Verifier}V</tex>. Так как <tex>\mathit{Prover}P</tex> заинтересован в том, чтобы <tex>\mathit{Verifier}V</tex> принял слово, ему необходимо угадать правильный ответ (иначе <tex>\mathit{Verifier}V</tex> просто вернёт <tex>0</tex>). Вероятность того, что <tex>\mathit{Verifier}V</tex> примет слово <tex>x</tex>, когда оно не принадлежит языку (то есть <tex>\mathit{Prover}P</tex> два раза подряд верно угадает номер графас вероятностью <tex> 0.5 </tex>), равна <tex>\frac{1}0.25</tex>. Значит soundness равна <tex> 0.75 </tex>, что больше или равно <tex> 2/{43}</tex>.
Таким образом, построенный протокол удовлетворяет условию теоремы.
}}
