Polylogarithmic-round interactive proofs for coNP collapse the exponential hierarchy

• Published in: Theoretical computer science 2007-10, Vol.385 (1), p.167-178
• Main Authors: Pavan, A., Selman, Alan L., Sengupta, Samik, Vinodchandran, N.V.
• Format: Article
• Language: English
• Subjects: Algorithmics. Computability. Computer arithmetics; Applied sciences; Complexity classes; Computer science; control theory; systems; Exact sciences and technology; Interactive proof systems; Logic and foundations; Mathematical logic, foundations, set theory; Mathematics; Miscellaneous; Non-uniform complexity; Recursion theory; Sciences and techniques of general use; Theoretical computing
• ISSN: 0304-3975; 1879-2294
• DOI: 10.1016/j.tcs.2007.06.013

If every language in coNP has a constant-round interactive proof system, then the polynomial-time hierarchy collapses [R.B. Boppana, J. Håstad, S. Zachos, Does co-NP have short interactive proofs? Information Processing Letters 25 (2) (1987) 127–132]. On the other hand, the well-known LFKN protocol gives O ( n ) -round interactive proof systems for all languages in coNP [C. Lund, L. Fortnow, H. Karloff, N. Nisan, Algebraic methods for interactive proof systems, Journal of the Association for Computing Machinery 39 (4) (1992) 859–868]. We consider the question of whether it is possible for coNP to have interactive proof systems with polylogarithmic-round complexity. We show that this is unlikely by proving that if a coNP-complete set has a polylogarithmic-round interactive proof system, then the exponential-time hierarchy collapses. We also consider exponential versions of the Karp–Lipton theorem and Yap’s theorem.