ECCC-Report TR04-007https://eccc.weizmann.ac.il/report/2004/007Comments and Revisions published for TR04-007en-usMon, 10 May 2004 09:42:30 +0300
Comment 1
| Explanation of revision |
Alan L. Selman,
Samik Sengupta
https://eccc.weizmann.ac.il/report/2004/007#comment1Please 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.
Mon, 10 May 2004 09:42:30 +0300https://eccc.weizmann.ac.il/report/2004/007#comment1
Revision 1
| Polylogarithmic-round Interactive Proofs for coNP Collapse the Exponential Hierarchy |
Alan L. Selman,
Samik Sengupta
https://eccc.weizmann.ac.il/report/2004/007#revision1Wed, 05 May 2004 00:00:00 +0300https://eccc.weizmann.ac.il/report/2004/007#revision1
Paper TR04-007
| Polylogarithmic-round Interactive Proofs for coNP Collapses the Exponential Hierarchy |
Alan L. Selman,
Samik Sengupta
https://eccc.weizmann.ac.il/report/2004/007It 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}.
Thu, 22 Jan 2004 16:49:35 +0200https://eccc.weizmann.ac.il/report/2004/007