Arthur-Merlin protocol
From Wikipedia, the free encyclopedia
In computational complexity theory, an Arthur-Merlin protocol is an interactive proof system in which the verifier's coin tosses are constrained to be public (i.e, known to the prover too). This notion was introduced by Babai et al. They proved that all languages with constant-length interactive proofs with private coins also have interactive proofs with public coins. Later, Goldwasser and Sipser generalized this result to proofs of arbitrary length.
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); but Merlin is not necessarily honest, so Arthur must analyze the information provided by Merlin in response to Arthur's queries and decide the problem itself. A problem is considered to be decidable if whenever the answer is "yes", Merlin has some series of responses which will cause Arthur to accept at least 2/3 of the time, and if whenever the answer is "no", Arthur will never accept more than 1/3 of the time. Thus, Arthur acts as a BPP verifier, assuming it is allotted polynomial time to make its decisions and queries.
The complexity class AM (or AM[1]) is the set of decision problems that can be decided in polynomial time by an Arthur-Merlin protocol where there is only one query/response pair. The complexity class AM[k] is the set of problems that can be decided in polynomial time, with k queries and responses.
The complexity class MA is the set of decision problems that can be decided in polynomial time with (unlimited) communication only from Merlin to Arthur.
For any fixed k, the class AM[k] is equal to AM[1]. It is open whether AM and MA are different. Moreover 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.
MA contains both NP and BPP. 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. MA is contained in AM, since Arthur need only send a void "query" at the start, to which Merlin will respond with the information it needs to send under the MA protocol. Both MA and AM are contained in the polynomial hierarchy. In particular, MA is contained in the intersection of Σ2P and Π2P and AM is contained in Π2P. MA is also contained in NP/poly, the class of decision problems computable with in non-deterministic polynomial time with a polynomial size advice.
See also: IP for a class with more than a constant number of interactions.
