Does co-NP have short interactive proofs ? (Q1108004): Difference between revisions

\textit{L. Babai} [Proc. 17th ACM Symp. Theor. Comput., 421-429 (1985)] and \textit{S. Goldwasser}, \textit{S. Micali} and \textit{C. Rackoff} [ibid., 291-304 (1985)] introduced two probabilistic extensions of the complexity class NP. The two complexity classes, denoted AM[Q] and \({\mathbb{P}}[Q]\), respectively, are defined using randomized interactive proofs between a prover and a verifier. \textit{S. Goldwasser} and \textit{M. Sipser} [Proc. 18th ACM Symp. Theor. Comput., 59-68 (1986)] proved that the two classes are equal. We prove that if the complexity class co-NP is contained in \({\mathbb{P}}[k]\) for some constant k (i.e., if every language in co-NP has a short interactive proof), then the polynomial-time hierarchy collapses to the second level. As a corollary, we show that if the graph isomorphism problem is NP-complete, then the polynomial-time hierarchy collapses.