108
правок
Изменения
Нет описания правки
Проверим полноту и обоснованность:
* '''Полнота''': если графы неизоморфны, то существует <tex>\pi</tex> такая, что всякий её символ равен 1 или 2 и задан корректно. Тогда на этой <tex>\pi</tex> верификатор всегда вернёт 1.
* '''Обоснованность''': если графы изоморфны, то благодаря случайному выбору <tex>i</tex> вероятность ошибки не превышает <tex>{}^1/{}^2_2</tex>.
}}
