ДОКАЗАТЕЛЬСТВО ИЗОМОРФИЗМА ГРАФОВ | Протокол GI | |
Протокол интерактивного доказательства | Протокол доказательства с нулевым разглашением |
Постановка задачи |
Пусть |
Описание протокола |
Общий вход: пара графов 1) Первый шаг доказывающего. Доказывающий
Доказывающий отправляет Примечание. Если входные графы изоморфны, как утверждает доказывающий, то граф, отправленный на первом шаге изоморфен обоим входным графам. А если входные графы не изоморфны, то никакой граф не может быть изоморфным обоим входным графам. 2) Первый шаг проверяющего. После получения графа 3) Второй шаг доказывающего. Если сообщение, полученное от проверяющего, равно 2, то доказывающий отправляет 4) Второй шаг проверяющего. Если сообщение обозначаемое |
|
|
|
|