GNI — различия между версиями
(Новая страница: «=== Определение === Проблема '''GNI''' = <tex>\{\langle G_1, G_2\rangle : G_1</tex> неизоморфен <tex>G_2\}</tex> == Формулиро…») |
(нет различий)
|
Версия 15:21, 5 мая 2010
Определение
Проблема GNI =
неизоморфенФормулировка задачи
GNI ∈ IP
Доказательство
Построим вероятностную машину Verifier, которая будет проверять за полиномиальное время работы и полиномиальное число вызовов к машине Prover, действительно ли два данных графа являются неизоморфными. При этом Prover может работать столько времени, сколько ему надо.
- Verifier случайным образом выбирает число .
- Verifier строит новый граф , изоморфный графу , перенумеровав в нём вершины случайным образом.
- Verifier отдаёт граф на проверку Prover
- Prover проверяет, какому из графов изоморфен граф . Если графы и неизоморфны, то Prover легко определит, какому из них изоморфен граф . В таком случае Prover возвращает . Иначе же для Prover графы изоморфны. Но у него нет возможности определить, с помощью какого графа Verifier построил граф . Поэтому в этом случае Prover возвращает .
- Verifier возвращает 1, если , и 0 в противном случае.
Такой Verifier всегда выдаст единицу, если графы неизоморфны, а, если они изоморфны, выдаст единицу с вероятностью
. Чтобы уменьшить вероятность ошибки, надо повторить шаги 1-5 несколько раз, при этом на шаге 5 Verifier ничего не возвращает, а сохраняет получившийся результат. В конце возвращается 1, если при выполнении шагов 1-5 единиц получилось больше, и 0 в противном случае.Таким образом,