210
правок
Изменения
Нет описания правки
{{Определение
|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>. Обратное утверждение сохраняется по предположению идеальной достоверности.
|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>.
