Комментарии 13
Интересно, можно ли разработать алгоритм для случая, когда у "доказывающего" есть не сам граф, а доказательство его существования (не конструктивное).
Или для Гамильтонова цикла такое доказательство трудно придумать?
en.wikipedia.org/wiki/Hamiltonian_path_problem
соответствующих краям цикла Гамильтона
Это вы «edge» так перевели?
И почему тогда нет указания, что это перевод?
Поясню, что мне кажется подозрительным. Если бы это была ваша статья, то вряд ли бы вы оставили в стороне очевидный выход для доказывающей стороны:
при ответе на первый вопрос показывать единички для произвольной перестановки вершин, а при ответе на второй — произвольный изоморфизм.
Ведь оба вопроса одновременно задавать нельзя.
Это решаемая проблема, но ваше изложение уж слишком упрощённое.
Например, можно заранее передавать матрицу, шифруя каждую ячейку уникальным публичным ключом, а "вскрытие карточек" осуществлять путем передачи соответствующих приватных ключей. Тогда принимающая сторона узнает только часть информации, но будет уверена, что доказывающий знает всю матрицу.
Что-то непонятно.
Доказывающий (жулик) создаёт две матрицы: одна для исходного графа (его перестановка), другая — для заведомо закольцованного (тупо с V вершинами и V рёбрами, например).
Проверяющий просит: "открой мне цикл" — доказывающий открывает цикл во второй матрице.
Просит: "открой мне граф" — открывает первую.
Если проверяющий просит: "открой мне весь граф и покажи на нём цикл" — это, извините, отнюдь не нулевое знание.
Потому что задача нахождения изоморфизма графов — хоть и NP-полная, но решаемая. А в некоторых случаях решаемая довольно легко.
Больше того: проверяющий даже без "покажи на нём цикл" должен выполнить эту сверку.
А то мало ли, жулик ему не тот граф всучил.
Чтобы жулик не жульничал с двумя матрицами, но и не давал проверяльщику халяву, — нужен какой-то нотариус, который получает ровно одну матрицу с нарисованным на ней циклом, но при этом сам не заинтересованный в доказательстве.
С другой стороны, если такой нотариус есть, то зачем нужен проверяльщик? Нотариус убедится, что доказательство верное, и скажет: "да, жулик не ворует, мамой клянусь (а теперь заплатите госпошлину)".
Молчание — золото: доказательство существования Гамильтонова цикла в графе