Интерактивное доказательство для HORN-SAT?

10

Есть ли способ, которым проверяющий может убедить верификатора в том, что некоторое выражение HORN-SAT выполнимо?

Конечно, это может показаться глупым, поскольку для HORN-SAT существуют линейные алгоритмы времени. С другой стороны, HORN-SAT является P-полным, что означает, что он не имеет алгоритмов лог-пространства, если P = L. Соответственно, ограничьте вычислительные возможности верификатора до L. Теперь верификатор очень слаб, поэтому проблема больше не глупая.

Еще один поворот в том, может ли это быть доказательством с нулевым знанием.

cc.complexity-theory interactive-proofs zero-knowledge Шон Харкер
источник
1
В случае с ненулевым знанием, я думаю, что для наивной проверки с использованием удовлетворительного назначения истины в качестве сертификата требуется только пространство журнала, при условии, что входные данные и сертификат записаны на лентах только для чтения, которые не учитываются как пространство.
Цуёси Ито
@Tsuyoshi: я не вижу, как сделать наивную проверку только в лог-пространстве. Если бы мы могли, разве это не показывало бы, что HORN-SAT находится в NL, и, таким образом, по P-полноте дает P = NL?
Шон Харкер
Нет. Я предположил, что сертификат находится на ленте только для чтения, что отличается от проверки, выполненной NL.
Цуёси Ито
@Tsuyoshi: Ах, так что вы можете прочитать сертификат много раз, тогда как определение NL на основе сертификата будет иметь сертификат, который может быть прочитан только один раз.
Шон Харкер

Ответы:

11

Этот http://www.cs.ubc.ca/~condon/papers/ips-survey.pdf обзор Энн Кондон содержит много фактов о ограниченных в пространстве интерактивных системах доказательства.

Существует несколько моделей, и основные отличия заключаются в том, разрешаете ли вы частные монеты для верификатора (IP) или только для публичных монет (AM), а также ограничиваете ли вы время проверки полиномом (не подразумевается только пробелом).

Без ограничения по времени ответ - да: IP (пространство журнала) содержит EXP, а AM (пространство журнала) = P.

Обратите внимание, что IP (пространство журнала), скорее всего, больше, чем стандартный IP. С другой стороны, IP (log-space, poly-time) = IP = PSPACE.

AM (log-space, poly-time) = P из-за «Делегирования вычислений: интерактивные доказательства для магглов» Голдвассера и др., STOC 2008.

Кроме того, статья Килиана (FOCS 88) «Нулевое знание с верификаторами пространства журналов» показывает, как получить систему доказательств с нулевым знанием времени логарифмического пространства для всего, что связано с IP (очевидно, с частными монетами).

Хартмут Клаук
источник
1
Я также нашел документ под названием « Делегирование вычислений: интерактивные доказательства для магглов» . Показывает ли теорема 3 этой работы, что AM (log-space, poly-time) = P?
Шон Харкер
Да, они действительно показывают это!
Хартмут Клаук