Comments 13

Интересно, можно ли разработать алгоритм для случая, когда у "доказывающего" есть не сам граф, а доказательство его существования (не конструктивное).
Или для Гамильтонова цикла такое доказательство трудно придумать?

Как я понимаю, существование Гамильтонова цикла можно строго доказать в графах специального вида (теорема Оре), но в таких графах и сам цикл ищется за полиномиальное время. По-видимому, задача доказательства существования цикла в произвольном графе равносильна задаче нахождения самого цикла (которая, естественно, NP-полная).
соответствующих краям цикла Гамильтона

Это вы «edge» так перевели?
И почему тогда нет указания, что это перевод?
Это «неточность» из разряда «с прямым углом перепутал».
Поясню, что мне кажется подозрительным. Если бы это была ваша статья, то вряд ли бы вы оставили в стороне очевидный выход для доказывающей стороны:
при ответе на первый вопрос показывать единички для произвольной перестановки вершин, а при ответе на второй — произвольный изоморфизм.
Ведь оба вопроса одновременно задавать нельзя.
Это решаемая проблема, но ваше изложение уж слишком упрощённое.

Например, можно заранее передавать матрицу, шифруя каждую ячейку уникальным публичным ключом, а "вскрытие карточек" осуществлять путем передачи соответствующих приватных ключей. Тогда принимающая сторона узнает только часть информации, но будет уверена, что доказывающий знает всю матрицу.

Кажется, этого мало.
Пусть доказывающий, не зная истинного цикла, при ответе на первый вопрос выбирает произвольную перестановку вершин и открывает соответствующие карточки. Как проверяющий поймёт, что его пытаются обмануть?

Но ведь, если эти карточки все состоят из единиц, то доказывающий случайно нашел гамильтонов цикл и ни капельки не соврал. Если же там нули где-то, то проверяющий видит попытку обмана.

Что-то непонятно.
Доказывающий (жулик) создаёт две матрицы: одна для исходного графа (его перестановка), другая — для заведомо закольцованного (тупо с V вершинами и V рёбрами, например).
Проверяющий просит: "открой мне цикл" — доказывающий открывает цикл во второй матрице.
Просит: "открой мне граф" — открывает первую.


Если проверяющий просит: "открой мне весь граф и покажи на нём цикл" — это, извините, отнюдь не нулевое знание.
Потому что задача нахождения изоморфизма графов — хоть и NP-полная, но решаемая. А в некоторых случаях решаемая довольно легко.
Больше того: проверяющий даже без "покажи на нём цикл" должен выполнить эту сверку.
А то мало ли, жулик ему не тот граф всучил.


Чтобы жулик не жульничал с двумя матрицами, но и не давал проверяльщику халяву, — нужен какой-то нотариус, который получает ровно одну матрицу с нарисованным на ней циклом, но при этом сам не заинтересованный в доказательстве.
С другой стороны, если такой нотариус есть, то зачем нужен проверяльщик? Нотариус убедится, что доказательство верное, и скажет: "да, жулик не ворует, мамой клянусь (а теперь заплатите госпошлину)".

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

Only those users with full accounts are able to leave comments. Log in, please.