Editing Arthur–Merlin protocol (section)

==Properties==

[[File:Arthur-Merlin classes diagram.svg|alt=A diagram showcasing the relationships of MA and AM with other complexity classes described in the article.|thumb|Known relationships of '''MA''' and '''AM''' with other complexity classes. An arrow from class ''A'' to class ''B'' means ''A'' is a subset of ''B''.]]

* 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.<ref>For a proof, see {{cite web|url=http://www.cs.cornell.edu/courses/cs6810/2009sp/scribe/lecture17.pdf|title=Lecture 17: Arthur-Merlin games, Zero-knowledge proofs|author=Rafael Pass and Jean-Baptiste Jeannin|date=March 24, 2009|access-date=June 23, 2010}}</ref>
* 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 (complexity)|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'''.<ref>{{Cite book |last1=Impagliazzo |first1=Russell |last2=Wigderson |first2=Avi |date=1997-05-04 |title=P = BPP if E requires exponential circuits: derandomizing the XOR lemma |publisher=ACM |pages=220–229 |doi=10.1145/258533.258590 |isbn=0897918886|s2cid=18921599 }}</ref>
* '''AM''' is the same as the class '''BP⋅NP''' where '''BP''' denotes the bounded-error probabilistic operator. Also, '''<math> \exists \cdot \mathsf{BPP}</math>''' ( also written as '''ExistsBPP''') is a subset of '''MA'''. Whether '''MA''' is equal to '''<math> \exists \cdot \mathsf{BPP}</math>''' 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 (complexity)|NP]]''' and '''[[BPP (complexity)|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 Σ<sub>2</sub><sup>P</sup> and Π<sub>2</sub><sup>P</sup> and '''AM''' is contained in Π<sub>2</sub><sup>P</sup>. Even more, '''MA''' is contained in subclass '''[[S2P (complexity)|{{nowrap|S{{su|p=P|b=2}}}}]]''',<ref>{{cite web|url=http://www.ccs.neu.edu/home/koods/papers/russell98symmetric.pdf |title=Symmetric Alternation captures BPP|website=Ccs.neu.edu|access-date=2016-07-26}}</ref> 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 (complexity)|advice]]. The proof is a variation of [[P/poly#Adleman's theorem|Adleman's theorem]].
* '''MA''' is contained in '''[[PP (complexity)|PP]]'''; this result is due to Vereshchagin.<ref>{{Cite book|last=Vereschchagin|first=N.K. |pages=138–143 |doi=10.1109/sct.1992.215389|isbn=081862955X|year=1992|chapter=On the power of PP |title=&#91;1992&#93; Proceedings of the Seventh Annual Structure in Complexity Theory Conference |s2cid=195705029 }}</ref>
* '''MA''' is contained in its quantum version, '''[[QMA]]'''.<ref>{{Cite journal |last1=Vidick |first1=Thomas |last2=Watrous |first2=John |date=2016 |title=Quantum Proofs |journal=Foundations and Trends in Theoretical Computer Science |volume=11 |issue=1–2 |pages=1–215 |doi=10.1561/0400000068 |issn=1551-305X|arxiv=1610.01664 |s2cid=54255188 }}</ref>
* '''AM''' contains the [[graph isomorphism problem|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 '''[[Polynomial hierarchy|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 [[extended Riemann hypothesis|ERH]], that for any ''d'' the problem "Given a collection of multivariate polynomials <math>f_i</math> each with integer coefficients and of degree at most ''d'', do they have a common complex zero?" is in '''AM'''.<ref>{{cite web|url=http://people.csail.mit.edu/madhu/FT98/course.html |title=Course: Algebra and Computation |website=People.csail.mit.edu |access-date=2016-07-26}}</ref>