Изменения
Нет описания правки
==Доказательство==
Алгоритм работы машины '''<tex>V''' </tex> аналогичен алгоритму работы при доказательстве того, что '''[[GNI]]''' ∈ '''IP'''.
В строке <tex>\pi</tex> для каждого графа (введена некоторая нумерация графов) записано, кому из данных графов <tex>G_1, G_2</tex> он изоморфен.
# <tex>V</tex> случайным образом выбирает число <tex>i = rand(2)</tex>.
# <tex>V</tex> строит новый граф <tex>F</tex>, изоморфный графу <tex>G_i</tex>, перенумеровав в нём вершины случайным образом.
# <tex>V</tex> смотрит в <tex>\pi</tex> кому граф <tex>F</tex> изоморфен, пусть это <tex>j</tex>
# <tex>V</tex> возвращает 1, если <tex>j = i</tex>, и 0 в противном случае.
В случае, если графы неизоморфны, то в <tex>\pi</tex> для каждого графа однозначно определено, кому он изоморфен и потому, посмотрев на позицию соответствующую графу <tex>f</tex>, <tex>V</tex> точно получит <tex>j = i</tex>.
Если же графы изоморфны, то полученное <tex>j</tex> может быть равновероятно равно <tex>1</tex> или <tex>2</tex>, потому вероятность "обмана" <tex>V</tex> равна <tex>\frac{1}{2}</tex>.
