It is known \cite{BHZ87} that if every language in coNP has a
constant-round interactive proof system, then the polynomial hierarchy
collapses. On the other hand, Lund {\em et al}.\ \cite{LFKN92} have shown that
#SAT, the #P-complete function that outputs the number of satisfying
assignments of a Boolean formula, can be computed by a linear-round interactive protocol. As a consequence, the coNP-complete set
$\overline{SAT}$ has a proof system with linear rounds of interaction.
We show that if every set in coNP has a polylogarithmic-round
interactive protocol then the exponential hierarchy collapses to the
third level. In order to prove this, we obtain an
exponential version of Yap's result \cite{yap83}, and improve upon an
exponential version of the Karp-Lipton theorem \cite{kl80}, obtained
first by Buhrman and Homer \cite{bh92}.
Please read the revision and not the original report. The proof of Theorem 3.1 is incorrect in the original. The correct proof, in the revision, follows from a result of Goldreich, Vadhan, and Wigderson, ECCC TR01-046.
