Arthur-Merlin (AM)
The class of decision problems for which a “yes” answer can be verified by an Arthur-Merlin protocol, as follows.
Arthur, a BPP verifier, generates a “challenge” based on the input, and sends it together with his random coins to Merlin. Merlin sends back a response, and then Arthur decides whether to accept. Given an algorithm for Arthur, we require that
- If the answer is “yes,” then Merlin can act in such a way that Arthur accepts with probability at least 2/3 (over the choice of Arthur’s random bits).
- If the answer is “no,” then however Merlin acts, Arthur will reject with probability at least 2/3.
Surprisingly, it turns out that such a system is just as powerful as a private-coin one, in which Arthur does not need to send his random coins to Merlin GS86. So, Arthur never needs to hide information from Merlin.
Furthermore, define AM[k] similarly to AM, except that Arthur and Merlin have rounds of interaction. Then for all constant k>2, AM[k] = AM[2] = AM BS88. Also, the result of GS86 can then be stated as follows: IP[k] is contained in AM[k+2] for every k (constant or non-constant).