Arthur-Merlin protocol
|
|
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. Later, Goldwasser and Sipser proved that the set of languages that have interactive proofs with private coins also have interactive proofs with public coins.
A Merlin-Arthur protocol is an Arthur-Merlin protocol with communication only from the prover to the verifier.
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 Arthur communicates first, Merlin replies and both of them can only send one message to the other party. The complexity class AM[k] is the set of problems that can be decided in polynomial time, if Arthur communicates first, Merlin replies, then Arthur communicates, etc. and each party can communicate at most k times.
The complexity class MA is the set of decision problems that can be decided in polynomial time with 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.
MA contains both NP and BPP. MA is contained in AM. 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.