Arthur-Merlin Games: A Randomized Proof System, and a Hierarchy of Complexity Classes

Independently of GMR, and published in the same STOC ’85, was a paper of Babai, Trading Group Theory for Randomness. This paper was later published in journal version as Arthur-Merlin Games: A Randomized Proof System, and a Hierarchy of Complexity Classes, with Moran as a coauthor; in fact, this paper shared the first ever G ̈odel Prize with GMR. Babai had written a previous paper with Szemer ́edi in which he had shown that some certain group theory problems — e.g., for a matrix group over a finite field given by its generators, is its order at most k? — were in NP, subject to some unproven group-theoretic hypothesis. Babai wanted to get an unconditional result, so he independently introduced the notion of interactive proofs, albeit with public coin tosses, and showed his problem had constant-round interactive proofs. In particular, he gave the following definition:

Definition 2 AM[k] is the class of interactive proofs that have k rounds, where the verifier speaks first and has public coin tosses. (AM stands for Arthur-Merlin, Arthur being the verifier, Merlin the prover.) Babai also showed: Theorem 1 For all constant k, AM[k] = AM[2].