Изменения
Нет описания правки
# Получив ответ, сравним его с правильным ответом — числом <tex>i</tex>; <br/>
# Если полученный ответ не совпадёт с <tex>i</tex>, то вернём <tex>0</tex>; <br/>
# Иначе повторим первые пять шагов ещё два раза раз и перейдём к последнему шагу; <br/>
# Если мы ещё не вернули <tex>0</tex>, то вернём <tex>1</tex>.
Покажем, что это удовлетворяет ограничениям на <tex>\mathrm{IP[1]}</tex>.
Во-первых, очевидно, что число раундов не превосходит трёхдвух. <br/>
Рассмотрим теперь случаи
* <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>\frac{1}{84}</tex>.
Таким образом, построенный протокол удовлетворяет условию теоремы.
}}
