REPORTS > DETAIL:

### Revision(s):

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

#### Polylogarithmic-round Interactive Proofs for coNP Collapse the Exponential Hierarchy

Revision #1
Authors: Alan L. Selman, Samik Sengupta
Accepted on: 5th May 2004 00:00
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
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