Изменения
→Соотношения с другими классами теории сложности
{{Определение
|definition =
<b>Интерактивным протоколом</b> (англ. ''interactive proof systemprotocol'') <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> 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> в течение активной фазы, и это время ограничено полиномом от длины входа.
# <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>.
{{Определение
|definition =
Если для интерактивного протокола выполняется <tex> \forall x \in L \Rightarrow \exists P : \mathbb{P}(V_{P}(x) = 1) \geqslant c </tex>, то говорят, что он обладает свойством ''' completeness ''' (русск. ''полнота'') равным <tex> \alpha c </tex>.
}}
Если <tex>c = 1</tex> ('''perfect completeness'''(русск. ''идеальная полнота'')), то это означает, что никакое верное утверждение не отклоняется <tex> V </tex>.
{{Определение
|definition =
Если для интерактивного протокола выполняется <tex> \forall x \notin L \Rightarrow \forall P : \mathbb{P}(V_{P}(x) = 1) \leqslant 1 - s </tex>, то говорят, что он обладает свойством ''' soundness ''' (русск. ''достоверность'') равным <tex> \alpha s </tex>.
}}
Если <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>. Обратное утверждение сохраняется по предположению идеальной достоверности.
{{Определение
|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>.
|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>PV</tex> будет проверять на принадлежность слова <tex>x</tex> языку, используя сертификат, который он запросит у <tex>P</tex>. Так как <tex>P</tex> не ограничен в вычислительной мощности, он может подобрать подходящий сертификат и именно его и сообщит, так как он заинтересован в том, чтобы <tex>V</tex> принял слово. Для этого требуется лишь один раунд интерактивного протокола.
}}
|statement=<tex>\mathrm{GNI} \in \mathrm{IP}[1]</tex>.
|proof=
Пусть на вход подали пару графов <tex> \langle G_{0}, G_{1} \rangle </tex> и нужно определить изоморфны ли они.
Будем использовать следующий алгоритм для <tex>V</tex>:
# Возьмём случайное число <tex>i \in \{0, 1\}</tex> и [[Комбинаторные_объекты|случайную перестановку]] <tex>\pi</tex> с вероятностной ленты;
# Создадим новый граф<tex> G </tex>, перемешав вершины графа c номером <tex>i</tex> перестановкой <tex>\pi</tex>.# Перешлём <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>.
# Если полученный ответ не совпадёт с <tex>i</tex>, то вернём <tex>0</tex>.
*[[Классы NP и Σ₁]]
*[[Классы BPP и PP]]
== Источники информации ==
*[[wikipedia: Interactive_proof_system | Wikipedia {{---}} Interactive proof system]]
[[Категория: Теория сложности]]
[[Категория: Вероятностные сложностные классы]]
[[Категория: Интерактивные протоколы]]
