Ограничивает ли требование уникальности правильных ответов для Мерлина силу протоколов Артура-Мерлина?

15

Преамбула.

Класс сложности AM - это те проблемы, которые могут быть решены с помощью двухсторонней интерактивной системы доказательств между прувером «Мерлин» и верификатором «Артур». Проблема, которая проверяет некоторое свойство объекта X, заключается в AM, если:

  • Для случаев ДА для случайного сообщения «вызов» (полиномиальной длины) Артур с высокой вероятностью может сформулировать ответ (полиномиальной длины), который Артур может использовать в качестве доказательства того, что X обладает свойством;

  • Для NO случаев для случайного сообщения вызова Артур генерирует, с высокой вероятностью Merlin не может сформулировать любой ответ , который может быть использован в качестве доказательства собственности, испытываемый на X .

- Описанный класс не изменится, если мы потребуем, чтобы Мерлин дал полезный ответ не только с высокой вероятностью, но и на любой вызов, который может вызвать Артур; в этом случае мы могли бы сказать, что мы требуем, чтобы ответ Мерлина всегда был действительным для экземпляров ДА , и что Артур проверяет, является ли ответ правильным. Поэтому, если Мерлин когда-либо выдаст недопустимый ответ, Артур знает, что проблемный экземпляр НЕТ экземпляра. Это настройка, которую я предпочел бы рассмотреть.

Примером является неизоморфизм графов: при наличии графов G и H с одним и тем же набором меток вершин Артур может случайным образом выбрать один из графов и создать «зашифрованную» версию F , переставив ее метки вершин, отправив презентацию ее Мерлину. , Если два графика не изоморфны, Мерлин может определить, какой из G или H Артур выбрал, определив, является ли F  ≅  G или F  ≅  H , и может ответить, определив, какой из двух F изоморфен. Однако если два графа G и H изоморфны, Мерлин не может различить, какой графF пришел, и любой ответ, который он дает, может быть правильным только случайно. Таким образом, для случаев ДА Мерлин всегда может отправить действительный ответ на любой вызов; для НЕТ случаев любой ответ, который Мерлин мог бы послать, будет с высокой вероятностью недействительным.

В вышеупомянутой проблеме не только существует действительный ответ, который Мерлин может выдать Артуру для каждого вызова, но на самом деле существует уникальный действительный ответ: то есть  указать, какой из G или H Артур выбрал, учитывая, что это может быть определено идентификации, изоморфный F .

Вопрос.

Означает ли наложение ограничения по этим направлениям - что для экземпляров YES , для любого вызова, который Артур мог бы отправить, есть ровно один действительный ответ для Мерлина - приводить к более ограничительному классу в смысле получения класса, который не известен как равный AM ?

Ниль де Бодрап
источник
Прежде чем рассмотреть, равно ли оно AM или нет, я даже не вижу, как доказать, что NP содержится в вашем классе….
Tsuyoshi Ito
1
Если мы требуем, чтобы у Мерлина был один действительный ответ только с высокой вероятностью, тогда класс содержит NP (и, я полагаю, весь AM): мы можем заставить Артура выполнить сокращение Valiant – Vazirani до Unique-SAT.
Эмиль Йержабек поддерживает Монику
@ Эмиль: Я понимаю, что если «высокая вероятность» равна 1 / поли, но возможно ли увеличить эту вероятность, скажем, до константы?
Tsuyoshi Ito
Справедливо, на самом деле это довольно малая вероятность. Я не знаю, как сделать это константой.
Эмиль Йержабек поддерживает Монику
1
Вы рассматриваете протоколы с публичными монетами или с протоколами частных монет? Из определения кажется, что вы думаете о протоколах публичных монет, но протокол для неизоморфизма графов, который вы описали, не является протоколом публичных монет.
Цуёси Ито

Ответы:

1

В статье Койрана «Nullstellensatz» Гильберта в «Полиномиальной иерархии» представлен общедоступный протокол Артура-Мерлина, позволяющий установить, что система из м уравнений для N неизвестных имеет решение в СN , зависящее от обобщенной гипотезы Римана. Здесь Мерлин находит премьерп сЧАС(п)знак равно0 для некоторого случайного хэшаЧАС вместе с решением(a0,a1,,aN) каждого изм уравнениймодификацияп .

Если система уравнений не имеет решения модификацияп , то существует только конечное число п по модулю, для которого существует решение. Если у системы действительно есть решение модификацияп , то безусловно будет положительная плотность п с решением, и GRH допускает, что п с решением в некотором смысле «равнораспределены», так что Мерлин получает победу.

Хотя Koiran дает пример решаемой системы , где плотность п экспоненциально мала, Koiran предполагает , что если система разрешима в СN , то в большинстве случаев там будет большое число из п (и большое количество ) ; Действительно, около 1 - 1 / е простых чисел должно иметь решение IIRCC.a1-1/е

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

Различие простых систем уравнений с решениями по модулю многих п от жестких систем уравнений с несколькими или только одним п видимому, требует определения свойств группы Галуа системы уравнений.

Метки
источник