МЕНЮ

Каталог

ДОКАЗАТЕЛЬСТВО ЗНАНИЯ ГАМИЛЬТОНОВА ЦИКЛА Протокол HC
Протокол интерактивного доказательства Протокол доказательства с нулевым разглашением

 

Постановка задачи

Пусть $ P$ знает гамильтонов цикл графа. $ P$ хочет доказать $ V$ свое знание, не показывая сам гамильтонов цикл.
Описание протокола

Общий вход: Граф $ G=(V,E)$. Пусть $ n=vert V vert$ и $ V={N_1,N_2,...,N_n}$. 

Дополнительный вход доказывающего: Гамильтонов цикл графа $ G$. 

1) Первый шаг доказывающего. Доказывающий шифрует граф $ G$ с помощью ящиков. Для этого он наугад инъективно отображает $ n$ маркированных вершин в $ n$ маркированных ящиков $ B_1$, $ B_2$, ..., $ B_n$ таким образом, что каждая из $ n!$ перестановок вершин в ящики равновероятна. Для каждой пары ящиков $ (B_i,B_j)$ подготавливает ящик $ B_{i,j}$. Этот ящик должен содержать $ 1$, если вершина, содержащаяся в ящике $ B_i$, смежна с вершиной, содержащейся в ящике $ B_j$, и 0 в противном случае. Затем все $ n+ {nchoose 2}$ ящиков запирает и отправляет проверяющему. 

2) Первый шаг проверяющего. Проверяющий получает $ n+ {nchoose 2}$ маркированных ящиков. Теперь ему предоставлен выбор:

(1) Если он пожелает, доказывающий откроет все ящики. В этом случае проверяющий может проверить, что ящики содержат описание графа $ G$. (Например, если вершина $ N_1$смежна с вершиной $ N_2$ и с вершиной $ N_5$, но но не смежна ни с какими другими вершинами графа $ G$, и вершина $ N_1$ содержится в ящике $ B_i$, $ N_2$ вершина в ящике $ B_j$, $ N_5$ вершина в ящике $ B_k$, то $ 1$ должна содержаться в ящиках $ B_{i,j}$ и $ B_{i,k}$, и 0 в ящике $ B_{i,x}$ для любого другого значения $ x$).

(2) С другой стороны, если проверяющий пожелает, доказывающий откроет в точности $ n$ящиков $ B_{i,j}$, $ B_{j,k}$, $ B_{k,l}$, ..., , которые содержат гамильтонов цикл графа $ G$, и показать, что они все содержат $ 1$. Это доказывает существование гамильтонова цикла (в любом графе, представленном в ящиках). Так как $ B_i$ не открыты, последовательность вершин, определяющих гамильтонов цикл в графе $ G$ не раскрывается. 

Проверяющий наугад выбирает один из этих 2 вариантов (граф или гамильтонов цикл), и таким образом, оба варианта равновероятны. 

3) Второй шаг доказывающего. Доказывающий открывает соответствующие ящики. 

Шаги 1)-3) повторяются $ k$ раз. 

4) Заключительный шаг проверяющего. Проверяющий принимает доказательство, если доказывающий выполняет и в каждом случае правильно демонстрирует либо запрашиваемый граф $ G$, либо запрашиваемый гамильтонов цикл. В противном случае, отвергает.

 

Основные сведения

 
Ссылки
  • M.Blum, "How to Prove a Theorem So No One Else Can Claim It, " Proceedings of the International Congress of Mathematicians, Berkeley, CA, 1986, pp. 1444—1451