Editing Arthur–Merlin protocol (section)

==AM==
The [[complexity class]] '''AM''' (or '''AM[2]''') is the set of [[decision problem]]s that can be decided in polynomial time by an Arthur&ndash;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''|,
*if ''x'' is in ''L'', then <math>\Pr\nolimits_{y\in\{0,1\}^{p(n)}}(\exists z\in\{0,1\}^{q(n)}\,M(x,y,z)=1)\ge2/3,</math>
*if ''x'' is not in ''L'', then <math>\Pr\nolimits_{y\in\{0,1\}^{p(n)}}(\forall z\in\{0,1\}^{q(n)}\,M(x,y,z)=0)\ge2/3.</math>

The second condition here can be rewritten as 
*if ''x'' is not in ''L'', then <math>\Pr\nolimits_{y\in\{0,1\}^{p(n)}}(\exists z\in\{0,1\}^{q(n)}\,M(x,y,z)=1)\le1/3.</math>

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.