Изменения

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