Polylogarithmic-round Interactive Proofs for coNP Collapse the Exponential Hierarchy

[PostScript | PDF]

Abstract

If every language in coNP has constant round interactive proof system, then the polynomial-time hierarchy collapses. On the other hand, the well-known LFKN protocol gives O(n)-round interactive proof systems for all languages in coNP. We consider the question 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.