211
правок
Изменения
м
→Язык GNI
|statement=<tex>\mathrm{GNI} \in \mathrm{IP}[1]</tex>.
|proof=
Будем использовать следующий алгоритм для <tex>V\mathit{Verifier}</tex>:
# Возьмём случайное число <tex>i \in \{0, 1\}</tex> и случайную перестановку <tex>\pi</tex> с вероятностной ленты; <br/>
# Создадим новый граф, перемешав вершины графа c номером <tex>i</tex> перестановкой <tex>\pi</tex>; <br/>
# Перешлём <tex>P\mathit{Prover}</tex> полученный граф с просьбой определить, из какого из исходных графов он был получен; <br/>
# Получив ответ, сравним его с правильным ответом — числом <tex>i</tex>; <br/>
# Если полученный ответ не совпадёт с <tex>i</tex>, то вернём <tex>0</tex>; <br/>
Во-первых, очевидно, что число раундов не превосходит двух. <br/>
Рассмотрим теперь случаи
* <tex> \langle G, H \rangle \in \mathrm{GNI}</tex>. Тогда <tex>G</tex> и <tex>H</tex> неизоморфны и <tex>P\mathit{Prover}</tex> сможет определить какой граф был перемешан <tex>V\mathit{Verifier}</tex>. Таким образом, <tex>P\mathit{Prover}</tex> сможет два раза подряд вернуть правильный ответ и в итоге <tex>V\mathit{Verifier}</tex> вернёт 1.* <tex> \langle G, H \rangle \notin \mathrm{GNI}</tex>. Тогда <tex>G</tex> и <tex>H</tex> изоморфны и <tex>P\mathit{Prover}</tex> не сможет определить какой граф был перемешан <tex>V\mathit{Verifier}</tex>. Так как <tex>P\mathit{Prover}</tex> заинтересован в том, чтобы <tex>V\mathit{Verifier}</tex> принял слово, ему необходимо угадать правильный ответ (иначе <tex>V\mathit{Verifier}</tex> просто вернёт <tex>0</tex>). Вероятность того, что <tex>V\mathit{Verifier}</tex> примет слово <tex>x</tex>, когда оно не принадлежит языку (то есть <tex>P\mathit{Prover}</tex> два раза подряд верно угадает номер графа), равна <tex>\frac{1}{4}</tex>.
Таким образом, построенный протокол удовлетворяет условию теоремы.
}}
