Does co-NP have short interactive proofs ? (English) Zbl 0653.68037

L. Babai [Proc. 17th ACM Symp. Theor. Comput., 421-429 (1985)] and S. Goldwasser, S. Micali and 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. S. Goldwasser and 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.


68Q25 Analysis of algorithms and problem complexity
03D15 Complexity of computation (including implicit computational complexity)
Full Text: DOI


[1] Aiello, W.; Goldwasser, S.; Hastad, J., On the power of interaction, (), 368-379
[2] Babai, L., Trading group theory for randomness, (), 421-429
[3] Bennett, C.G.; Gill, J., Relative to a random oracle A, \( P\^{}\{A\} ≠ NP\^{}\{A\} ≠ co-NP\^{}\{A\}\) with probability 1, SIAM J. comput., 10, 1, 96-113, (1981)
[4] Chernoff, H., A measure of asymptotic efficiency for tests of a hypothesis based on the sum of observations, Ann. math. statist., 23, 493-509, (1952) · Zbl 0048.11804
[5] Condon, A.; Ladner, R., Probabilistic game automata, (), 144-162
[6] L. Fortnow and M. Sipser, Private communication.
[7] Gill, J., Computational complexity of probabilistic Turing machines, SIAM J. comput., 6, 4, 675-695, (1977) · Zbl 0366.02024
[8] Goldreich, O.; Micali, S.; Wigderson, A., Proofs that yield nothing but their validity and a methodology of cryptographic protocol design, (), 174-187
[9] Goldwasser, S.; Micali, S.; Rackoff, C., The knowledge complexity of interactive proof systems, (), 291-304 · Zbl 0900.94025
[10] Goldwasser, S.; Sipser, M., Private coins versus public coins in interactive proof systems, (), 59-68
[11] Hinman, P.; Zachos, S., Probabilistic machines, oracles and quantifiers, (), 159-192
[12] Ko, K., Some observations on probabilistic algorithms and NP-hard problems, Inform. process. lett., 14, 1, 39-43, (1982) · Zbl 0483.68045
[13] Schöning, U., A low and high hierarchy within NP, J. comput. system sci., 27, 14-28, (1983)
[14] Schöning, U., Graph isomorphism is in the low hierarchy, (1986), Preprint
[15] Sipser, M., A complexity theoretic approach to randomness, (), 330-335
[16] Stockmeyer, L.J., The polynomial-time hierarchy, Theoret. comput. sci., 3, 1, 1-22, (1976) · Zbl 0353.02024
[17] Zachos, S., Probabilistic quantifiers, adversaries, and complexity classes: an overview, (), 383-400
[18] Zachos, S.; Fürer, M., Probabilistic quantifiers vs. distrustful adversaries, (1985), Preprint · Zbl 0647.68052
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.