Протокол Артура–Мерлина
Интерактивная система доказательств в теории сложности вычислений

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

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

МА

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

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

  • если x находится в L , то ∃ з ∈ { 0 , 1 } д ( н ) Пр у ∈ { 0 , 1 } п ( н ) ( М ( х , у , з ) = 1 ) ≥ 2 / 3 , {\displaystyle \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 , то ∀ з ∈ { 0 , 1 } д ( н ) Пр у ∈ { 0 , 1 } п ( н ) ( М ( х , у , з ) = 0 ) ≥ 2 / 3. {\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 , то ∀ z ∈ { 0 , 1 } q ( n ) Pr y ∈ { 0 , 1 } p ( n ) ( M ( x , y , z ) = 1 ) ≤ 1 / 3. {\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 |,

  • если x находится в L , то Pr y ∈ { 0 , 1 } p ( n ) ( ∃ z ∈ { 0 , 1 } q ( n ) M ( x , y , z ) = 1 ) ≥ 2 / 3 , {\displaystyle \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 y ∈ { 0 , 1 } p ( n ) ( ∀ z ∈ { 0 , 1 } q ( n ) M ( x , y , z ) = 0 ) ≥ 2 / 3. {\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 , то Pr y ∈ { 0 , 1 } p ( n ) ( ∃ z ∈ { 0 , 1 } q ( n ) M ( x , y , z ) = 1 ) ≤ 1 / 3. {\displaystyle \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] начнется с одного сообщения от Мерлина Артуру, затем сообщения от Артура Мерлину и, наконец, сообщения от Мерлина Артуру. Последнее сообщение всегда должно быть от Мерлина Артуру, так как Артуру никогда не поможет отправка сообщения Мерлину после принятия решения о своем ответе.

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

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

Ссылки

  1. ↑ Доказательство см. в книге Рафаэля Пасса и Жана-Батиста Жаннина (24 марта 2009 г.). "Лекция 17: Игры Артура-Мерлина, доказательства с нулевым разглашением" (PDF) . Получено 23 июня 2010 г.
  2. ^ Импальяццо, Рассел; Вигдерсон, Ави (1997-05-04). P = BPP, если E требует экспоненциальных цепей: дерандомизация леммы XOR . ACM. стр.  220–229 . doi :10.1145/258533.258590. ISBN 0897918886. S2CID  18921599.
  3. ^ "Симметричное чередование захватывает BPP" (PDF) . Ccs.neu.edu . Получено 2016-07-26 .
  4. ^ Верещагин, NK (1992). «О силе PP». [1992] Труды Седьмой ежегодной конференции по теории структур в сложности . С.  138–143 . doi :10.1109/sct.1992.215389. ISBN 081862955X. S2CID  195705029.
  5. ^ Видик, Томас; Уотроус, Джон (2016). «Квантовые доказательства». Основы и тенденции в теоретической информатике . 11 ( 1– 2): 1– 215. arXiv : 1610.01664 . doi :10.1561/0400000068. ISSN  1551-305X. S2CID  54255188.
  6. ^ "Курс: Алгебра и вычисления". People.csail.mit.edu . Получено 26.07.2016 .

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

  • Бабай, Ласло (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.
  • Курс Мадху Судана в Массачусетском технологическом институте по повышенной сложности
Retrieved from "https://en.wikipedia.org/w/index.php?title=Arthur–Merlin_protocol&oldid=1219765283"