Протокол Артура-Мерлина - Arthur–Merlin protocol

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

Учитывая двух участников протокола, которых зовут Артур и Мерлин соответственно, основное предположение состоит в том, что Артур является стандартным компьютером (или верификатором), оснащенным устройством генерации случайных чисел , в то время как Мерлин фактически является оракулом с бесконечной вычислительной мощностью (также известный как доказывающий ). Однако Мерлин не обязательно честен, поэтому Артур должен проанализировать информацию, предоставленную Мерлином в ответ на запросы Артура, и решить проблему самостоятельно. Проблема не считается решаемая этим протоколом , если всякий раз , когда ответ «да», Merlin имеет некоторую серию ответов , которые будут вызывать Артур принять по крайней мере , ⁺² / ₊₃ времени, и если каждый раз , когда ответ «нет» Артур никогда не будет принимать более ¹ / ₃ времени. Таким образом, Артур действует как вероятностный проверяющий с полиномиальным временем, предполагая, что ему отведено полиномиальное время для принятия своих решений и запросов.

MA

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

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

• если x находится в L , то ${\ Displaystyle \ существует z \ in \ {0,1 \} ^ {q (n)} \, \ Pr \ nolimits _ {y \ in \ {0,1 \} ^ {p (n)}} (M (x, y, z) = 1) \ geq 2/3,}$
• если x не в L , то ${\ displaystyle \ 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 , то ${\ displaystyle \ 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 , то ${\ Displaystyle \ Pr \ nolimits _ {y \ in \ {0,1 \} ^ {p (n)}} (\ существует z \ in \ {0,1 \} ^ {q (n)} \, M (x, y, z) = 1) \ geq 2/3,}$
• если x не в L , то ${\ Displaystyle \ 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 , то ${\ Displaystyle \ Pr \ nolimits _ {y \ in \ {0,1 \} ^ {p (n)}} (\ существует z \ in \ {0,1 \} ^ {q (n)} \, M (x, y, z) = 1) \ leq 1/3.}$

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

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

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

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

• И 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 обозначает вероятностный оператор с ограниченной ошибкой. Кроме того, (также обозначаемый как ExistsBPP ) является подмножеством MA . Равна ли MA - вопрос открытый. ${\ Displaystyle \ существует \ cdot {\ mathsf {BPP}}}$${\ Displaystyle \ существует \ cdot {\ mathsf {BPP}}}$
• Преобразование в протокол частных монет, в котором Мерлин не может предсказать результат случайных решений Артура, в общем случае увеличит количество раундов взаимодействия не более чем на 2. Таким образом, версия AM с приватными монетами равна версии с публичными монетами.
• MA содержит как NP, так и BPP . Для BPP это происходит немедленно, поскольку Артур может просто проигнорировать Мерлина и решить проблему напрямую; для NP Мерлину нужно только отправить Артуру сертификат, который Артур может подтвердить детерминированно за полиномиальное время.
• И MA, и AM содержатся в полиномиальной иерархии . В частности, МА содержится в пересечении Е ₂ ^Р и П ₂ ^Р и М. содержится в П ₂ ^P . Более того, MA содержится в подклассе S ^P
  ₂ , класс сложности, выражающий «симметричное чередование». Это обобщение теоремы Зипсера – Лаутеманна .
• AM содержится в NP / poly , классе задач принятия решений, вычисляемых за недетерминированное полиномиальное время с советом по размеру полинома . Доказательство представляет собой вариацию теоремы Адлемана .
• MA содержится в PP ; этот результат принадлежит Верещагину.
• MA содержится в своей квантовой версии QMA .
• AM содержит проблему определения того, не изоморфны ли два графа . Протокол, использующий частные монеты, следующий и может быть преобразован в протокол общедоступных монет. Учитывая два графа G и H , Артур случайным образом выбирает один из них и выбирает случайную перестановку его вершин, представляя переставленный граф I Мерлину. Мерлин должен ответить , если я был создан из G или H . Если графы неизоморфны, Мерлин сможет ответить с полной уверенностью (проверив , изоморфен ли I G ). Однако, если графики изоморфны, возможно, что G или H использовались для создания I , и одинаково вероятно. В этом случае Мерлин не имеет возможности отличить их друг от друга и может убедить Артура с вероятностью не более 1/2, и это можно увеличить до 1/4 повторением. На самом деле это доказательство с нулевым разглашением .
• Если AM содержит coNP, то PH = AM . Это свидетельствует о том, что изоморфизм графов вряд ли будет NP-полным, поскольку влечет коллапс полиномиальной иерархии.
• Известно, в предположении ERH , что для любого d возникает проблема: «Имеется ли набор многомерных многочленов, каждый с целыми коэффициентами и степенью не выше d , имеют ли они общий комплексный нуль?» сейчас AM . ${\ displaystyle f_ {i}}$

Рекомендации

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

• Бабай, Ласло (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 .
• Курс MIT Мадху Судана по продвинутой сложности

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

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