210
правок
Изменения
м
Нет описания правки
{{Определение
|definition =
<b>Интерактивным протоколом</b> (англ. ''interactive proof system'') <tex> \langle P, V \rangle </tex>, разрешающим язык <tex>L</tex>, называется абстрактная машина (см. рисунок), моделирующая вычисления как обмен сообщениями между двумя программами (где <tex>P</tex> означает <tex> \mathitmathrm{Prover}</tex> и <tex> V </tex> означает <tex>\mathitmathrm{Verifier}</tex>), такими, что# <tex>P</tex> заинтересован в том, чтобы <tex>V</tex> решил, что слово <tex>x</tex> принадлежит языку;.# <tex>P</tex> не ограничен по времени вычисления и памяти;.# <tex>V</tex> заинтересован установить, действительно ли слово <tex>x</tex> принадлежит языку;.# <tex>V</tex> {{---}} [[Вероятностные вычисления. Вероятностная машина Тьюринга|вероятностная машина Тьюринга]];.
# <tex>V</tex> ограничен полиномиальным временем работы.
}}
Интерактивные протоколы делятся на два типа в зависимости от доступа <tex>P</tex> к вероятностной ленте <tex>V</tex>:
# ''' public coins ''' (русск. ''открытые монеты'') {{---}} <tex>P</tex> может видеть вероятностную ленту <tex>V</tex>;# ''' private coins ''' (русск. ''закрытые монеты''){{---}} <tex>P</tex> <b>не</b> может видеть вероятностную ленту <tex>V</tex>.
{{Определение
|definition =
Если для интерактивного протокола выполняется <tex> \forall x \in L \Rightarrow \exists P : \mathbb{P}(V_{P}(x) = 1) \geqslant \alpha </tex>, то говорят, что он обладает свойством ''' completeness ''' (русск. ''полнота'') равным <tex> \alpha </tex>.
}}
Если completeness равно <tex>1</tex>, это означает, что никакое верное утверждение не отклоняется <tex> V </tex>.
{{Определение
|definition =
Если для интерактивного протокола выполняется <tex> \forall x \notin L \Rightarrow \forall P : \mathbb{P}(V_{P}(x) = 1) \leqslant 1 - \alpha </tex>, то говорят, что он обладает свойством ''' soundness ''' (русск. ''достоверность'') равным <tex> \alpha </tex>.
}}
Если soundness равно <tex> 1 </tex>, это означет, что если утверждение ложно, то никакой <tex>P</tex> не может убедить <tex>V</tex>, что утверждение истино.
|definition =
<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>;.# soundness <tex> \geqslant 2 /{3} </tex>;.
# число раундов интерактивного протокола <tex> O(f(n)), n = |x|\}</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>;.# soundness <tex> \geqslant 2 /{3} </tex>;.
# число раундов интерактивного протокола <tex> O(f(n)), n = |x|\}</tex>.
}}
Будем использовать следующий алгоритм для <tex>V</tex>:
# Возьмём случайное число <tex>i \in \{0, 1\}</tex> и [[Комбинаторные_объекты|случайную перестановку]] <tex>\pi</tex> с вероятностной ленты;
# Создадим новый граф, перемешав вершины графа c номером <tex>i</tex> перестановкой <tex>\pi</tex>;.# Перешлём <tex>P</tex> полученный граф с просьбой определить, из какого из исходных графов он был получен;.# Получив ответ, сравним его с правильным ответом — числом <tex>i</tex>;.# Если полученный ответ не совпадёт с <tex>i</tex>, то вернём <tex>0</tex>;.# Иначе повторим первые пять шагов ещё раз и перейдём к последнему шагу;.
# Если мы ещё не вернули <tex>0</tex>, то вернём <tex>1</tex>.
