Arthur–Merlin protocol

<h2 id="ma">MA</h2>
The simplest such protocol is the 1-message protocol where Merlin sends Arthur a message, and then Arthur decides whether to accept or not by running a probabilistic polynomial time computation. (This is similar to the verifier-based definition of NP, the only difference being that Arthur is allowed to use randomness here.) Merlin does not have access to Arthur's coin tosses in this protocol, since it is a single-message protocol and Arthur tosses his coins only after receiving Merlin's message. This protocol is called MA. Informally, a <a href="/facts/Formal_language/crDTyP8q">language</a> L is in MA if for all strings in the language, there is a polynomial sized proof that Merlin can send Arthur to convince him of this fact with high probability, and for all strings not in the language there is no proof that convinces Arthur with high probability.
Formally, the complexity class MA is the set of decision problems that can be decided in polynomial time by an Arthur–Merlin protocol where Merlin's only move precedes any computation by Arthur. In other words, a language L is in MA if there exists a polynomial-time deterministic Turing machine M and polynomials p, q such that for every input string x of length n = |x|,

<ul><li>if x is in L, then 
 
 
 
 ∃
 z
 ∈
 {
 0
 ,
 1
 
 }
 
 q
 (
 n
 )
 
 
 
 
 Pr
 
 y
 ∈
 {
 0
 ,
 1
 
 }
 
 p
 (
 n
 )
 
 
 
 
 (
 M
 (
 x
 ,
 y
 ,
 z
 )
 =
 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,}
 
</li>
<li>if x is not in L, then 
 
 
 
 ∀
 z
 ∈
 {
 0
 ,
 1
 
 }
 
 q
 (
 n
 )
 
 
 
 
 Pr
 
 y
 ∈
 {
 0
 ,
 1
 
 }
 
 p
 (
 n
 )
 
 
 
 
 (
 M
 (
 x
 ,
 y
 ,
 z
 )
 =
 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.}
 
</li></ul>
The second condition can alternatively be written as

<ul><li>if x is not in L, then 
 
 
 
 ∀
 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.}
 
</li></ul>
To compare this with the informal definition above, z is the purported proof from Merlin (whose size is bounded by a polynomial) and y is the random string that Arthur uses, which is also polynomially bounded.

<h2 id="am">AM</h2>
The <a href="/facts/Complexity_class/IIKrcTbP">complexity class</a> AM (or AM[2]) is the set of <a href="/facts/Decision_problem/cQNWjbdE">decision problems</a> that can be decided in polynomial time by an Arthur–Merlin protocol with two messages. There is only one query/response pair: Arthur tosses some random coins and sends the outcome of all his coin tosses to Merlin, Merlin responds with a purported proof, and Arthur deterministically verifies the proof. In this protocol, Arthur is only allowed to send outcomes of coin tosses to Merlin, and in the final stage Arthur must decide whether to accept or reject using only his previously generated random coin flips and Merlin's message.
In other words, a language L is in AM if there exists a polynomial-time deterministic Turing machine M and polynomials p, q such that for every input string x of length n = |x|,

<ul><li>if x is in L, then 
 
 
 
 
 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,}
 
</li>
<li>if x is not in L, then 
 
 
 
 
 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.}
 
</li></ul>
The second condition here can be rewritten as 

<ul><li>if x is not in L, then 
 
 
 
 
 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.}
 
</li></ul>
As above, z is the alleged proof from Merlin (whose size is bounded by a polynomial) and y is the random string that Arthur uses, which is also polynomially bounded.
The complexity class AM[k] is the set of problems that can be decided in polynomial time, with k queries and responses. AM as defined above is AM[2]. AM[3] would start with one message from Merlin to Arthur, then a message from Arthur to Merlin and then finally a message from Merlin to Arthur. The last message should always be from Merlin to Arthur, since it never helps for Arthur to send a message to Merlin after deciding his answer.

<h2 id="properties">Properties</h2>

<ul><li>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.<a class="footnote-ref" id="fnref:1" href="#fn:1">1</a></li>
<li>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, <a href="/facts/IP_(complexity)/j79Dv0nv">IP</a>, which is known to be equal to <a href="/facts/PSPACE/RIkAClvG">PSPACE</a> and is widely believed to be stronger than the class AM[2].</li>
<li>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.</li>
<li>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.<a class="footnote-ref" id="fnref:2" href="#fn:2">2</a></li>
<li>AM is the same as the class BP⋅NP where BP denotes the bounded-error probabilistic operator. Also, 
 
 
 
 ∃
 ⋅
 
 
 B
 P
 P
 
 
 
 
 {\displaystyle \exists \cdot {\mathsf {BPP}}}
 
 ( also written as ExistsBPP) is a subset of MA. Whether MA is equal to 
 
 
 
 ∃
 ⋅
 
 
 B
 P
 P
 
 
 
 
 {\displaystyle \exists \cdot {\mathsf {BPP}}}
 
 is an open question.</li>
<li>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.</li>
<li>MA contains both <a href="/facts/NP_(complexity)/6muUfVMI">NP</a> and <a href="/facts/BPP_(complexity)/6woy25bz">BPP</a>. 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.</li>
<li>Both MA and AM are contained in the <a href="/facts/Polynomial_hierarchy/73N468Dv">polynomial hierarchy</a>. 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 href="/facts/S2P_(complexity)/E1dqVcMJ">SP2</a>,<a class="footnote-ref" id="fnref:3" href="#fn:3">3</a> a complexity class expressing "symmetric alternation". This is a generalization of <a href="/facts/Sipser%E2%80%93Lautemann_theorem/sqEGkrqg">Sipser–Lautemann theorem</a>.</li>
<li>AM is contained in <a href="/facts/NP/poly/t5P8Notp">NP/poly</a>, the class of decision problems computable in non-deterministic polynomial time with a polynomial size <a href="/facts/Advice_(complexity)/ldFxPTzd">advice</a>. The proof is a variation of <a href="/facts/P/poly/cHXNlnYJ">Adleman's theorem</a>.</li>
<li>MA is contained in <a href="/facts/PP_(complexity)/WCLqxQF8">PP</a>; this result is due to Vereshchagin.<a class="footnote-ref" id="fnref:4" href="#fn:4">4</a></li>
<li>MA is contained in its quantum version, <a href="/facts/QMA/AtQsb09s">QMA</a>.<a class="footnote-ref" id="fnref:5" href="#fn:5">5</a></li>
<li>AM contains the <a href="/facts/Graph_isomorphism_problem/Buhk3qsS">problem</a> 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 <a href="/facts/Zero_knowledge_proof/38soaPT5">zero knowledge proof</a>.</li>
<li>If AM contains coNP then <a href="/facts/Polynomial_hierarchy/73N468Dv">PH</a> = AM. This is evidence that graph isomorphism is unlikely to be NP-complete, since it implies collapse of polynomial hierarchy.</li>
<li>It is known, assuming <a href="/facts/Extended_Riemann_hypothesis/17nLmBbu">ERH</a>, that for any d the problem "Given a collection of multivariate polynomials 
 
 
 
 
 f
 
 i
 
 
 
 
 {\displaystyle f_{i}}
 
 each with integer coefficients and of degree at most d, do they have a common complex zero?" is in AM.<a class="footnote-ref" id="fnref:6" href="#fn:6">6</a></li></ul>

<h2 id="bibliography">Bibliography</h2>
<ul><li><a href="/facts/L%C3%A1szl%C3%B3_Babai/6yflmWJv">Babai, László</a> (1985), "Trading group theory for randomness", STOC '85: Proceedings of the seventeenth annual ACM symposium on Theory of computing, ACM, pp. 421–429, <a href="/facts/ISBN_(identifier)/15AdSPa9">ISBN</a> 978-0-89791-151-1.</li>
<li><a href="/facts/Shafi_Goldwasser/aTJJq4mB">Goldwasser, Shafi</a>; <a href="/facts/Michael_Sipser/h5Wg22bh">Sipser, Michael</a> (1986), "Private coins versus public coins in interactive proof systems", STOC '86: Proceedings of the eighteenth annual ACM symposium on Theory of computing, ACM, pp. 59–68, <a href="/facts/ISBN_(identifier)/15AdSPa9">ISBN</a> 978-0-89791-193-1.</li>
<li><a href="/facts/Sanjeev_Arora/W3C8BLQI">Arora, Sanjeev</a>; Barak, Boaz (2009), <a href="http://www.cs.princeton.edu/theory/complexity/">Computational Complexity: A Modern Approach</a>, <a href="/facts/Cambridge_University_Press/fgEBSSRq">Cambridge</a>, <a href="/facts/ISBN_(identifier)/15AdSPa9">ISBN</a> 978-0-521-42426-4.</li>
<li><a href="http://theory.lcs.mit.edu/~madhu/ST05/">Madhu Sudan's MIT course on advanced complexity</a></li></ul>
<h2 id="external-links">External links</h2>
<ul><li><a href="/facts/Complexity_Zoo/htGK5zuz">Complexity Zoo</a>: <a href="https://complexityzoo.net/Complexity_Zoo:M#ma">MA</a></li>
<li><a href="/facts/Complexity_Zoo/htGK5zuz">Complexity Zoo</a>: <a href="https://complexityzoo.net/Complexity_Zoo:A#am">AM</a></li></ul>

<h2 id="references">References</h2>

<ol>
<li id="fn:1">For a proof, see Rafael Pass and Jean-Baptiste Jeannin (March 24, 2009). "Lecture 17: Arthur-Merlin games, Zero-knowledge proofs" (PDF). Retrieved June 23, 2010. <a href="http://www.cs.cornell.edu/courses/cs6810/2009sp/scribe/lecture17.pdf" target="_blank">http://www.cs.cornell.edu/courses/cs6810/2009sp/scribe/lecture17.pdf</a> <a href="#fnref:1" class="footnote-back-ref">↩</a></li>
<li id="fn:2">Impagliazzo, Russell; Wigderson, Avi (1997-05-04). P = BPP if E requires exponential circuits: derandomizing the XOR lemma. ACM. pp. 220–229. doi:10.1145/258533.258590. ISBN 0897918886. S2CID 18921599. <a href="0897918886" target="_blank">0897918886</a> <a href="#fnref:2" class="footnote-back-ref">↩</a></li>
<li id="fn:3">"Symmetric Alternation captures BPP" (PDF). Ccs.neu.edu. Retrieved 2016-07-26. <a href="http://www.ccs.neu.edu/home/koods/papers/russell98symmetric.pdf" target="_blank">http://www.ccs.neu.edu/home/koods/papers/russell98symmetric.pdf</a> <a href="#fnref:3" class="footnote-back-ref">↩</a></li>
<li id="fn:4">Vereschchagin, N.K. (1992). "On the power of PP". [1992] Proceedings of the Seventh Annual Structure in Complexity Theory Conference. pp. 138–143. doi:10.1109/sct.1992.215389. ISBN 081862955X. S2CID 195705029. <a href="081862955X" target="_blank">081862955X</a> <a href="#fnref:4" class="footnote-back-ref">↩</a></li>
<li id="fn:5">Vidick, Thomas; Watrous, John (2016). "Quantum Proofs". Foundations and Trends in Theoretical Computer Science. 11 (1–2): 1–215. arXiv:1610.01664. doi:10.1561/0400000068. ISSN 1551-305X. S2CID 54255188. <a href="/wiki/ArXiv_(identifier)" target="_blank">/wiki/ArXiv_(identifier)</a> <a href="#fnref:5" class="footnote-back-ref">↩</a></li>
<li id="fn:6">"Course: Algebra and Computation". People.csail.mit.edu. Retrieved 2016-07-26. <a href="http://people.csail.mit.edu/madhu/FT98/course.html" target="_blank">http://people.csail.mit.edu/madhu/FT98/course.html</a> <a href="#fnref:6" class="footnote-back-ref">↩</a></li>
</ol>

Arthur–Merlin protocol open-in-new

Arthur–Merlin protocol