Преамбула.
Класс сложности 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 ?
источник
Ответы:
В статье Койрана «Nullstellensatz» Гильберта в «Полиномиальной иерархии» представлен общедоступный протокол Артура-Мерлина, позволяющий установить, что система изм уравнений для N неизвестных имеет решение в СN , зависящее от обобщенной гипотезы Римана. Здесь Мерлин находит премьерп сЧАС( р ) = 0 для некоторого случайного хэшаЧАС вместе с решением( а0,1, ⋯ , аN) каждого изм уравнениймод р .
Если система уравнений не имеет решениямод р , то существует только конечное число п по модулю, для которого существует решение. Если у системы действительно есть решение мод р , то безусловно будет положительная плотность п с решением, и GRH допускает, что п с решением в некотором смысле «равнораспределены», так что Мерлин получает победу.
Хотя Koiran дает пример решаемой системы , где плотностьп экспоненциально мала, Koiran предполагает , что если система разрешима в СN , то в большинстве случаев там будет большое число из п (и большое количество ) ; Действительно, около 1 - 1 / е простых чисел должно иметь решение IIRCC.a 1 - 1 / е
Таким образом, в вышеупомянутой проблеме не только существует действительный ответ, который Мерлин может дать Артуру для каждого вызова, но на самом деле может быть большое количество действительных ответов.
Различие простых систем уравнений с решениями по модулю многихп от жестких систем уравнений с несколькими или только одним п видимому, требует определения свойств группы Галуа системы уравнений.
источник