Протокол Артура-Мерлина

В теории сложности вычислений протокол Артура-Мерлина , представленный Бабаем (1985) , представляет собой интерактивную систему доказательства , в которой подбрасывания монеты проверяющим ограничены публичностью (т.е. известны также и доказывающему). Голдвассер и Сипсер (1986) доказали, что все (формальные) языки с интерактивными доказательствами произвольной длины с частными монетами также имеют интерактивные доказательства с публичными монетами.

Учитывая двух участников протокола, называемых Артуром и Мерлином соответственно, основное предположение состоит в том, что Артур — это стандартный компьютер (или верификатор), оснащенный устройством генерации случайных чисел , в то время как Мерлин фактически является оракулом с бесконечной вычислительной мощностью (также известным как доказывающее устройство). ). Однако Мерлин не обязательно честен, поэтому Артур должен проанализировать информацию, предоставленную Мерлином в ответ на запросы Артура, и самому решить проблему. Проблема считается разрешимой с помощью этого протокола, если всякий раз, когда ответ «да», Мерлин имеет некоторую серию ответов, которые заставят Артура принять хотя бы 2 ⁄ 3 случаев, и если каждый раз ответ будет «нет», Артур никогда не примет больше, чем 1/3 ​ времени . Таким образом, Артур действует как вероятностный верификатор с полиномиальным временем, предполагая, что ему выделено полиномиальное время для принятия решений и запросов.

И

Самый простой такой протокол — это протокол с одним сообщением, где Мерлин отправляет Артуру сообщение, а затем Артур решает, принимать его или нет, путем выполнения вероятностного полиномиального вычисления времени. (Это похоже на определение NP, основанное на верификаторе, с той лишь разницей, что Артуру здесь разрешено использовать случайность.) Мерлин не имеет доступа к подбрасыванию монеты Артуром в этом протоколе, поскольку это протокол с одним сообщением, и Артур бросает свои монеты только после получения сообщения Мерлина. Этот протокол называется MA . Неформально, язык L находится в MA , если для всех строк в языке существует доказательство полиномиального размера, которое Мерлин может послать Артуру, чтобы убедить его в этом факте с высокой вероятностью, а для всех строк, не входящих в язык, нет доказательства того, что убеждает Артура с большой вероятностью.

Формально класс сложности MA представляет собой набор задач решения, которые могут быть решены за полиномиальное время с помощью протокола Артура-Мерлина, где единственный ход Мерлина предшествует любому вычислению Артура. Другими словами, язык L находится в MA , если существует детерминированная машина Тьюринга M с полиномиальным временем и полиномы p , q такие, что для каждой входной строки x длины n = | х |,

• если x находится в L , то $\exists z\in \{0,1\}^{q(n)}\,\Pr \nolimits _{y\in \{0,1\}^{p(n)}}(M(x,y,z)=1)\geq 2/3,$
• если x не находится в L , то $\forall z\in \{0,1\}^{q(n)}\,\Pr \nolimits _{y\in \{0,1\}^{p(n)}}(M(x,y,z)=0)\geq 2/3.$

Второе условие можно альтернативно записать как

• если x не находится в L , то $\forall z\in \{0,1\}^{q(n)}\,\Pr \nolimits _{y\in \{0,1\}^{p(n)}}(M(x,y,z)=1)\leq 1/3.$

Если сравнить это с приведенным выше неформальным определением, z — это предполагаемое доказательство Мерлина (размер которого ограничен полиномом), а y — это случайная строка, которую использует Артур, которая также полиномиально ограничена.

ЯВЛЯЮСЬ

Класс сложности AM (или AM[2] ) представляет собой набор задач решения , которые могут быть решены за полиномиальное время с помощью протокола Артура-Мерлина с двумя сообщениями. Существует только одна пара запрос/ответ: Артур подбрасывает несколько случайных монет и отправляет результаты всех своих подбрасываний Мерлину, Мерлин отвечает предполагаемым доказательством, а Артур детерминированно проверяет это доказательство. В этом протоколе Артуру разрешено отправлять Мерлину только результаты подбрасывания монеты, и на заключительном этапе Артур должен решить, принять или отклонить, используя только свои ранее сгенерированные случайные подбрасывания монеты и сообщение Мерлина.

Другими словами, язык L находится в AM , если существует детерминированная машина Тьюринга M с полиномиальным временем и полиномы p , q такие, что для каждой входной строки x длины n = | х |,

• если x находится в L , то $\Pr \nolimits _{y\in \{0,1\}^{p(n)}}(\exists z\in \{0,1\}^{q(n)}\,M(x,y,z)=1)\geq 2/3,$
• если x не находится в L , то $\Pr \nolimits _{y\in \{0,1\}^{p(n)}}(\forall z\in \{0,1\}^{q(n)}\,M(x,y,z)=0)\geq 2/3.$

Второе условие здесь можно переписать как

• если x не находится в L , то $\Pr \nolimits _{y\in \{0,1\}^{p(n)}}(\exists z\in \{0,1\}^{q(n)}\,M(x,y,z)=1)\leq 1/3.$

Как и выше, z — предполагаемое доказательство Мерлина (размер которого ограничен полиномом), а y — случайная строка, которую использует Артур, которая также полиномиально ограничена.

Класс сложности AM[ k ] — это набор задач, которые можно решить за полиномиальное время с помощью k запросов и ответов. AM, как определено выше, представляет собой AM[2] . AM[3] начинался с одного сообщения от Мерлина Артуру, затем сообщения от Артура Мерлину и, наконец, сообщения от Мерлина Артуру. Последнее сообщение всегда должно быть от Мерлина Артуру, поскольку Артуру никогда не поможет отправить сообщение Мерлину после того, как он определится с ответом.

Характеристики

Известны связи МА и АМ с другими классами сложности. Стрелка из класса A в класс B означает, что является подмножеством B. A

• И MA , и AM остаются неизменными, если их определения изменяются так, чтобы требовать совершенной полноты, а это означает, что Артур принимает с вероятностью 1 (вместо 2/3), когда x присутствует в языке.
• Для любой константы k ≥ 2 класс AM[ k ] равен AM[2] . Если k может быть полиномиально связано с входным размером, класс AM [poly( n )] равен классу IP , который, как известно, равен PSPACE и, как широко распространено мнение, более сильный, чем класс AM[2] .
• MA содержится в AM , поскольку AM [3] содержит MA : Артур может после получения сертификата Мерлина подбросить необходимое количество монет, отправить их Мерлину, а ответ проигнорировать.
• остается открытым ли AM и MA, Вопрос о том, различны . Согласно правдоподобным нижним границам схемы (аналогичным тем, что подразумевают P = BPP ), они оба равны NP .
• AM — это то же самое, что класс BP⋅NP , где BP обозначает вероятностный оператор с ограниченной ошибкой. Также, $\exists \cdot {\mathsf {BPP}}$ (также пишется как ExistsBPP ) является подмножеством MA . ли MA Равен $\exists \cdot {\mathsf {BPP}}$ это открытый вопрос.
• Переход к протоколу приватной монеты, в котором Мерлин не может предсказать исход случайных решений Артура, увеличит количество раундов взаимодействия максимум на 2 в общем случае. Таким образом, версия AM для частной монеты равна версии для публичной монеты.
• MA содержит как NP , так и BPP . Для BPP это немедленно, поскольку Артур может просто игнорировать Мерлина и решить проблему напрямую; для NP Мерлину нужно только отправить Артуру сертификат, который Артур может проверить детерминированно за полиномиальное время.
• И MA , и AM содержатся в полиномиальной иерархии . В частности, MA содержится в пересечении Σ ₂ ^П и П ₂ ^П и AM содержится в Π ₂ ^П . Более того, MA содержится в подклассе S. ^П
  ₂ , класс сложности, выражающий «симметричное чередование». Это обобщение теоремы Сипсера–Лаутмана .
• AM содержится в NP/poly , классе задач решения, вычисляемых за недетерминированное полиномиальное время с полиномиальным размером рекомендации . Доказательство представляет собой вариацию теоремы Адлемана .
• МА содержится в ПП ; этот результат принадлежит Верещагину.
• MA содержится в своей квантовой версии QMA .
• AM содержит проблему определения того, не являются ли два графа изоморфными. Протокол, использующий частные монеты, приведен ниже и может быть преобразован в протокол общедоступных монет. Учитывая два графа G и H , Артур случайным образом выбирает один из них и выбирает случайную перестановку его вершин, предоставляя перестановочный граф I Мерлину. Мерлин должен ответить, был ли создан из G или H. я Если графы неизоморфны, Мерлин сможет ответить с полной уверенностью (проверив, ли I изоморфен G ). Однако, если графы изоморфны, возможно, что G или H использовались для создания I , и это одинаково вероятно. В этом случае Мерлин не имеет возможности отличить их друг от друга и может убедить Артура с вероятностью не более 1/2, которую можно увеличить до 1/4 повторением. Фактически это доказательство с нулевым разглашением .
• Если AM содержит coNP , то PH = AM . Это свидетельствует о том, что изоморфизм графов вряд ли будет NP-полным, поскольку он предполагает коллапс полиномиальной иерархии.
• Известно, предполагая ERH , что для любого d задача «Дана совокупность многомерных полиномов $f_{i}$ каждый с целыми коэффициентами и степени не выше d , имеют ли они общий комплексный ноль?" находится в AM .

Библиография

• Бабай, Ласло (1985), «Теория торговых групп для случайности», STOC '85: Материалы семнадцатого ежегодного симпозиума ACM по теории вычислений , ACM, стр. 421–429, ISBN  978-0-89791-151-1 .
• Гольдвассер, Шафи ; Сипсер, Майкл (1986), «Частные монеты по сравнению с публичными монетами в интерактивных системах доказательств», STOC '86: Материалы восемнадцатого ежегодного симпозиума ACM по теории вычислений , ACM, стр. 59–68, ISBN  978-0-89791-193-1 .
• Арора, Санджив ; Барак, Воаз (2009), Сложность вычислений: современный подход , Кембридж , ISBN  978-0-521-42426-4 .
• Курс Мадху Судана в Массачусетском технологическом институте по повышенной сложности

Внешние ссылки

• Зоопарк сложности : Массачусетс
• Зоопарк сложности : AM