Задача «Изоморфизм графа»
Приведем в качестве примера протокол доказательства с абсолютно нулевым разглашением для языка «Изоморфизм графов» из работы[GMW]. Входным словом является пара графов G1=(U,Е1) и G0=(U,E0). Здесь U - множество вершин, которое можно отождествить с множеством натуральных чисел {1,...,n}, Е1
и Е0 множества ребер такие, что |Е1|=|Е0|=m. Графы G1 и G2 называются изоморфными, если существует перестановка на множестве U такая, что (u,v)ÎЕ0
тогда и только тогда, когда (j(u),j(v))ÎЕ1
(обозначается G1=jG0). Задача распознавания изоморфизма графов хорошо известная математическая задача, для которой на данный момент неизвестно полиномиальных алгоритмов ее решения. С другой стороны, неизвестно, является ли эта задача NР-полной, хотя есть веские основания предполагать, что не является.
Протокол IG
Пусть j изоморфизм между G1 и G0. Следующие четыре шага выполняются в цикле m раз, каждый раз с независимыми случайными величинами.
1. Р
выбирает случайную перестановку p на множестве U, вычисляет Н=-тG1 и посылает этот граф V.
2. V
выбирает случайный бит a и посылает его Р.
3. Если a=1, то Р посылает V перестановку p, в противном случае - перестановку p°j.
4. Если перестановка, полученная V, не является изоморфизмом между Ga
и Н, то V останавливается и отвергает доказательство. В противном случае выполнение протокола продолжается.
Если проверки п.4 дали положительный результат во всех m циклах, то V
принимает доказательство.
Необходимо отметить, что если в протоколе IG машина Р
получает изоморфизм в качестве дополнительного входного слова, то ей для выполнения протокола не требуются неограниченные вычислительные ресурсы. Более того, в этом случае Р может быть полиномиальной вероятностной шиной Тьюринга.
Теорема 4.1. Протокол
IG является доказательством с абсолютно нулевым разглашением для языка «Изоморфизм графов».
Доказательство.
Подробно приведено в работе [Ва1].
