40
правок
Изменения
Нет описания правки
# Если мы ещё не вернули <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.
