Эквивалентность двух определений полноты и обоснованности в интерактивных системах доказательства

11

Полнота и обоснованность интерактивных систем доказательства неформально определяются как:

  • Полнота: если утверждение верно, честный проверяющий может убедить честного проверяющего в этом факте whp .

  • Обоснованность: если утверждение ложно, обманщик не может убедить честного проверяющего (в достоверности ложного утверждения) whp

Термин «whp» либо интерпретируется как «с вероятностью, большей, чем (скажем) 2/3», либо «с вероятностью, большей, чем обратная величина любого полинома». Для последующего обсуждения кажется несущественным, какую интерпретацию «whp» выбрать.

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

Мне оба определения вероятности кажутся эквивалентными; пока я не могу доказать это. Я прав? Можете ли вы доказать их эквивалент?

cc.complexity-theory interactive-proofs неимоверный
источник
2
Вы также должны учитывать, имеете ли вы в виду «публичные» монеты или «частные» монеты. В общедоступных монетах как проверяющий, так и проверяющий знают результаты случайного выбора, а для частных монет проверяющий не знает случайного выбора проверяющего. В этом последнем случае вы заботитесь только о том, что делает верификатор, не глядя на проверяющего, потому что проверяющий просто не знает случайных бросков монет.
Маркос Вильягра
@Marcos: взгляните на оригинальное определение интерактивных доказательств, которое по своей природе является «частной» монетой. В последнем предложении первого столбца на странице 293, которое подчеркнуто, говорится, что «вероятности берутся только за собственные броски B». (Здесь B - это верификатор.) С другой стороны, журнальная версия вышеупомянутого документа позволяет принимать вероятности для подбрасывания монет обеих сторон. Это может быть источником путаницы, верно?
MS Dousti
@ Садек: Я вижу, я не знал об этой разнице между журналом и версиями конференции. Тем не менее, для частных монет я не вижу смысла принимать во внимание броски проверяющих монет, потому что он мог решить не говорить проверяющему об этом. Проверяющий является ответственным за принятие или отклонение решения, и он может не знать, что делает проверяющий.
Маркос Вильягра
1
@ Маркос: Вы правы, но те же рассуждения верны и для публичных монетных доказательств; поскольку в этих системах проверочные монеты все еще являются закрытыми (только монеты верификатора являются открытыми). В общем, можно рассмотреть детерминистский прувер: поскольку прувер всемогущ, ему не нужна случайность и он может выбрать оптимальный ответ детерминистически. Тем не менее, этот тип рассуждений не работает, если мы рассмотрим системы с нулевым знанием, в которых стратегия проверяющего должна быть вероятностной (в противном случае его знания утекут).
MS Dousti
2
(Продолжение) Если проверяющий рандомизирован, то я думаю, что правильная формулировка состоит в том, чтобы вычислить вероятность по броскам монет проверяющего и проверяющего: хотя, как сказал Маркос, проверяющее лицо отвечает за окончательное решение, ее решение принимается сделано (среди прочих) на основе сообщений, поступающих от проверяющего. Учитывая тот факт, что проверяющий рандомизирован, броски его монет, безусловно, влияют на сообщения, которые он отправляет. Таким образом, броски монет проверяющего влияют на вероятность принятия. Я прав?
MS Dousti

Ответы:

6

Прувер "всесилен и обладает неограниченными вычислительными ресурсами", поэтому ему не нужны случайные биты. Таким образом, единственная случайность - это случайность верификатора.

Если проверяющий использует случайные биты, он должен заменить их случайной битовой строкой, которая, скорее всего, заставит верификатор принять (это верно как для честного, так и для любого нечестного проверяющего). Кроме того, проверяющий может определить эту оптимальную битовую строку, поскольку проверяющий является «всесильным».

Тайсон Уильямс
источник
1
Как я сказал в комментарии выше, это верно только в том случае, если вы рассматриваете только интерактивные доказательства. Тем не менее, все будет по-другому, если принять во внимание другие свойства, такие как «нулевое знание», которое естественно связано с интерактивными доказательствами.
MS Dousti
1
Продолжение: В частности, Орен доказал следующее: «... в соответствии с определением вспомогательного ввода нулевого знания, случайность доказательства важна для нетривиальности систем доказательства с нулевым знанием. Другими словами, любой язык которая имеет вспомогательную систему ввода с нулевым знанием, в которой средство проверки является детерминированным для BPP. " (См. Раздел 4.5 Oren для получения дополнительной информации.) Следовательно, вы не всегда можете предполагать, что P является детерминированным.
MS Dousti