Editing Interactive proof system (section)

=== Arthur–Merlin and Merlin–Arthur protocols ===
{{main|Arthur–Merlin protocol}}
Although NP may be viewed as using interaction, it wasn't until 1985 that the concept of computation through interaction was conceived (in the context of complexity theory) by two independent groups of researchers. One approach, by  [[László Babai]], who published "Trading group theory for randomness",<ref>László Babai. [http://portal.acm.org/citation.cfm?id=22192 Trading group theory for randomness]. ''Proceedings of the Seventeenth Annual Symposium on the Theory of Computing'', ACM. 1985.</ref> defined the ''Arthur–Merlin'' ('''AM''') class hierarchy. In this presentation, Arthur (the verifier) is a [[probabilistic Turing machine|probabilistic]], polynomial-time machine, while Merlin (the prover) has unbounded resources.

The class '''MA''' in particular is a simple generalization of the NP interaction above in which the verifier is probabilistic instead of deterministic. Also, instead of requiring that the verifier always accept valid certificates and reject invalid certificates, it is more lenient:
* '''Completeness:''' if the string is in the language, the prover must be able to give a certificate such that the verifier will accept with probability at least 2/3 (depending on the verifier's random choices).
* '''Soundness:''' if the string is not in the language, no prover, however malicious, will be able to convince the verifier to accept the string with probability exceeding 1/3.

This machine is potentially more powerful than an ordinary NP [[interaction protocol]], and the certificates are no less practical to verify, since '''BPP''' algorithms are considered as abstracting practical computation (see [[Bounded-error probabilistic polynomial|BPP]]).