Интерактивные доказательства и классы сложности AM и MA

Введение

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

Свойства

И 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 и является открытым вопросом. Переход к протоколу с приватной монетой, в котором Мерлин не может предсказать исход случайных решений Артура, увеличит число раундов взаимодействия максимум на 2 в общем случае. Следовательно, версия AM с приватной монетой эквивалентна версии с публичной монетой. MA содержит как NP, так и BPP. Для BPP это очевидно, поскольку Артур может просто игнорировать Мерлина и решить задачу напрямую; для NP Мерлину достаточно отправить Артуру сертификат, который Артур может проверить детерминированно за полиномиальное время. И MA, и AM содержатся в полиномиальной иерархии. В частности, MA содержится в пересечении Σ2P и Π2P, а AM содержится в Π2P. Более того, MA содержится в подклассе , классе сложности, выражающем "симметричную альтернирующую" сложность. Это обобщение теоремы Сипсера — Лаутемана. AM содержится в NP/poly, классе задач принятия решений, разрешимых за недетерминированное полиномиальное время с полиномиальным советом. Доказательство является вариацией теоремы Адлемана. MA содержится в PP; этот результат принадлежит Верещагину. MA содержится в своей квантовой версии, QMA. AM содержит задачу определения, являются ли два графа неизоморфными. Протокол с использованием приватных монет выглядит следующим образом и может быть преобразован в протокол с публичными монетами. Даны два графа G и H, Артур случайным образом выбирает один из них и выбирает случайную перестановку его вершин, представляя Мерлину переставленный граф I. Мерлин должен ответить, был ли граф I создан из G или H. Если графы неизоморфны, Мерлин сможет ответить с полной уверенностью (проверив, изоморфен ли I графу G). Однако, если графы изоморфны, то возможно, что для создания I использовался либо G, либо H, с равной вероятностью. В этом случае Мерлин не может их различить и может убедить Артура с вероятностью не более 1/2, которую можно усилить до 1/4 путем повторения. Это, по сути, доказательство с нулевым разглашением. Если AM содержит coNP, то PH = AM. Это является свидетельством того, что изоморфизм графов вряд ли будет NP-полной задачей, поскольку это подразумевает схлопывание полиномиальной иерархии. Известно, что при предположении ERH для любого d задача "Дано множество многомерных полиномов, каждый с целочисленными коэффициентами и степенью не более d, имеют ли они общий комплексный корень?" принадлежит классу AM.

Both MA and AM remain unchanged if their definitions are changed to require perfect completeness, which means that Arthur accepts with probability 1 (instead of 2/3) when x is in the language. For any constant k ≥ 2, the class AM[k] is equal to AM[2]. If k can be polynomially related to the input size, the class AM[poly(n)] is equal to the class, IP, which is known to be equal to PSPACE and is widely believed to be stronger than the class AM[2]. MA is contained in AM, since AM[3] contains MA: Arthur can, after receiving Merlin's certificate, flip the required number of coins, send them to Merlin, and ignore the response. It is open whether AM and MA are different. Under plausible circuit lower bounds (similar to those implying P=BPP), they are both equal to NP. AM is the same as the class BP⋅NP where BP denotes the bounded error probabilistic operator. Also, ( also written as ExistsBPP) is a subset of MA. Whether MA is equal to is an open question. The conversion to a private coin protocol, in which Merlin cannot predict the outcome of Arthur's random decisions, will increase the number of rounds of interaction by at most 2 in the general case. So the private coin version of AM is equal to the public coin version. MA contains both NP and BPP. For BPP this is immediate, since Arthur can simply ignore Merlin and solve the problem directly; for NP, Merlin need only send Arthur a certificate, which Arthur can validate deterministically in polynomial time. Both MA and AM are contained in the polynomial hierarchy. In particular, MA is contained in the intersection of Σ2P and Π2P and AM is contained in Π2P. Even more, MA is contained in subclass , a complexity class expressing "symmetric alternation". This is a generalization of Sipser–Lautemann theorem. AM is contained in NP/poly, the class of decision problems computable in non deterministic polynomial time with a polynomial size advice. The proof is a variation of Adleman's theorem. MA is contained in PP; this result is due to Vereshchagin. MA is contained in its quantum version, QMA. AM contains the problem of deciding if two graphs are not isomorphic. The protocol using private coins is the following and can be transformed to a public coin protocol. Given two graphs G and H, Arthur randomly chooses one of them, and chooses a random permutation of its vertices, presenting the permuted graph I to Merlin. Merlin has to answer if I was created from G or H. If the graphs are nonisomorphic, Merlin will be able to answer with full certainty (by checking if I is isomorphic to G). However, if the graphs are isomorphic, it is both possible that G or H was used to create I, and equally likely. In this case, Merlin has no way to tell them apart and can convince Arthur with probability at most 1/2, and this can be amplified to 1/4 by repetition. This is in fact a zero knowledge proof. If AM contains coNP then PH = AM. This is evidence that graph isomorphism is unlikely to be NP complete, since it implies collapse of polynomial hierarchy. It is known, assuming ERH, that for any d the problem "Given a collection of multivariate polynomials each with integer coefficients and of degree at most d, do they have a common complex zero?" is in AM.