Arthur–Merlin protocol

In computational complexity theory, an Arthur–Merlin protocol, introduced by Babai (1985), is an interactive proof system in which the verifier's coin tosses are constrained to be public (i.e. known to the prover too).

Given two participants in the protocol called Arthur and Merlin respectively, the basic assumption is that Arthur is a standard computer (or verifier) equipped with a random number generating device, while Merlin is effectively an oracle with infinite computational power (also known as a prover).

Thus, Arthur acts as a probabilistic polynomial-time verifier, assuming it is allotted polynomial time to make its decisions and queries.

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.

The complexity class AM (or AM[2]) is the set of decision problems that can be decided in polynomial time by an Arthur–Merlin protocol with two messages.