Изменения

# ''Prover'' проверяет, какому из графов изоморфен граф <tex>F</tex>. Если графы <tex>G_1</tex> и <tex>G_2</tex> неизоморфны, то ''Prover'' легко определит, какому из них изоморфен граф <tex>F</tex>. В таком случае ''Prover'' возвращает <tex>j : G_i G_j \sim F</tex>. Иначе же для ''Prover'' графы <tex>G_1, G_2, F</tex> изоморфны. Но у него нет возможности определить, с помощью какого графа ''Verifier'' построил граф <tex>F</tex>. Поэтому в этом случае ''Prover'' возвращает <tex>j = rand(2)</tex>.

Такой ''Verifier'' всегда выдаст единицу, если графы неизоморфны, а, если они изоморфны, выдаст единицу с вероятностью <tex>1/2</tex>. Чтобы уменьшить вероятность ошибки, надо повторить шаги 1-5 несколько раз, при этом на шаге 5 ''Verifier'' ничего не возвращает, а сохраняет получившийся результат. В конце возвращается 1, если при выполнении шагов 1-5 единиц получилось большевсегда получались единицы, и 0 в противном случае.