Editing Arthur–Merlin protocol (section)

==MA==
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 [[formal language|language]] ''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''|,
*if ''x'' is in ''L'', then <math>\exists z\in\{0,1\}^{q(n)}\,\Pr\nolimits_{y\in\{0,1\}^{p(n)}}(M(x,y,z)=1)\ge2/3,</math>
*if ''x'' is not in ''L'', then <math>\forall z\in\{0,1\}^{q(n)}\,\Pr\nolimits_{y\in\{0,1\}^{p(n)}}(M(x,y,z)=0)\ge2/3.</math>

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

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.