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