Revision #1 Authors: Alan L. Selman, Samik Sengupta

Accepted on: 5th May 2004 00:00

Downloads: 3098

Keywords:

TR04-007 Authors: Alan L. Selman, Samik Sengupta

Publication: 22nd January 2004 16:49

Downloads: 3251

Keywords:

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}.

Comment #1 Authors: Alan L. Selman, Samik Sengupta

Accepted on: 10th May 2004 09:42

Downloads: 2158

Keywords:

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.