[BS88] Arthur-merlin games A randomized proof system and a hierarchy of complexity classes
Authors: Lázló Babai, Shlomo Moran | Venue: JCSS 1988 | Source
Abstract
One can view NP as the complexity class that captures the notion of efficient provability by classical (formal) proofs. We consider broader complexity classes (still “just above NP”), in the hope to formalize the notion of efficient provability by overwhelming statistical evidence. Such a concept should combine the nondeterministic nature of (classical) proofs and the statistical nature of conclusions via Monte Carlo algorithms such as a Solovay-Strassen style “proof’ of primality. To accomplish this goal, two randomized interactive proof systems have recently been offered independently by S. Goldwasser, S. Micah, and C. Rackoff (GMR system) (in “Proceedings, 17th ACM Symp. Theory of Comput., Providence, RI, 1985,” pp. 291-304) and by L. Babai (Arthur-Merlin system) (in “Proceedings, 17th ACM Symp. Theory of Comput., Providence, RI, 1985,” pp. 421429), respectively. The proving power of the two systems has subsequently been shown by S. Goldwasser and M. Sipser (in “Proceedings, 18th ACM Symp. Theory of Comput., Berkeley, CA, 1986”) to be equivalent. In both systems, a nondeterministic prover (Merlin) tries to convince a randomizing verifier (Arthur) that a certain string x belongs to a language L. The verifier operates under polynomial time constraint. The GMR system uses private coin tosses whereas in the Arthur-Merlin proof system, coin tosses are public. In this paper we give an exposition of the Arthur-Merlin system. We describe the resulting hierarchj of complexity classes AM(f(n)), where t(n) is the number of rounds of interaction on inputs of length n. The “Collapse Theorem” (Babai, lot. cif.) states that for r(n) > 2, AM(r(n) + 1) = AM(t(n)). In particular, the finite levels of the hierarchy collapse to AM gf AM(2). We prove the following stronger version (“Speedup Theorem”): for t(n) 2 2, AM(2t(n)) = AM(r(n)). This complements a result of W. Aiello, J. Hastad, and S. Goldwasser (in “Proceedings, 27th IEEE Symp. Found. of Comput. Sci., 1986,” pp. 368-379), saying that in a relativized world, no unbounded reduction of the number of rounds is possible. R. Boppana, J. Hastad, and S. Zachos provided a strong piece of evidence to support the view that AM is “not much larger” than NP by showing that if AM contains coNP then the polynomial time hierarchy collapses to x = AM. We show that this is an immediate consequence of the Collapse Theorem. A combination of the result of S. Goldwasser and M. Sipser, a striking observation by 0. Goldreich, S. Micali, and A. Widgerson, and the Collapse Theorem imply that graph non-isomorphism belongs to AM. We give a direct proof of this fact and generalize it to the coset intersection problem for permutation groups. In view of the Boppana-Hastad-Zachos result, one obtains the strongest evidence yet against NP-completeness of graph isomorphism and coset intersection. Using random oracles, we define the class almos&NP. This class, another natural randomized extension of NP, has, as an immediate consequence of recent work by Noam Nissan, turned out to be equal to AM. This provides additional evidence of the robustness of the class AM.