40
правок
Изменения
Нет описания правки
Рассмотрим теперь случаи
* <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}{48}</tex>.
Таким образом, построенный протокол удовлетворяет условию теоремы.
}}
