ECCC
Electronic Colloquium on Computational Complexity
Login | Register | Classic Style



REPORTS > DETAIL:

Revision(s):

Revision #1 to TR04-007 | 5th May 2004 00:00

Polylogarithmic-round Interactive Proofs for coNP Collapse the Exponential Hierarchy

RSS-Feed




Revision #1
Authors: Alan L. Selman, Samik Sengupta
Accepted on: 5th May 2004 00:00
Downloads: 871
Keywords: 


Abstract:


Paper:

TR04-007 | 13th January 2004 00:00

Polylogarithmic-round Interactive Proofs for coNP Collapses the Exponential Hierarchy





TR04-007
Authors: Alan L. Selman, Samik Sengupta
Publication: 22nd January 2004 16:49
Downloads: 974
Keywords: 


Abstract:

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(s):

Comment #1 to TR04-007 | 10th May 2004 09:42

Explanation of revision





Comment #1
Authors: Alan L. Selman, Samik Sengupta
Accepted on: 10th May 2004 09:42
Downloads: 640
Keywords: 


Abstract:

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.




ISSN 1433-8092 | Imprint