loading...
 This Article 
   
 Share 
   
 Bibliographic References 
   
 Add to: 
 
Digg
Furl
Spurl
Blink
Simpy
Google
Del.icio.us
Y!MyWeb
 
 Search 
   
19th Annual IEEE Conference on Computational Complexity (CCC'04)
Polylogarithmic-Round Interactive Proofs for coNP Collapse the Exponential Hierarchy
Amherst, Massachusetts
June 21-June 24
ISBN: 0-7695-2120-7
ASCII Text
x 
 
Alan L. Selman, Samik Sengupta, "Polylogarithmic-Round Interactive Proofs for coNP Collapse the Exponential Hierarchy," Computational Complexity, Annual IEEE Conference on, pp. 82-90, 19th Annual IEEE Conference on Computational Complexity (CCC'04), 2004.
 
 
BibTex
x
 
@article{ 10.1109/CCC.2004.1313805,
author = {Alan L. Selman and Samik Sengupta},
title = {Polylogarithmic-Round Interactive Proofs for coNP Collapse the Exponential Hierarchy},
journal ={Computational Complexity, Annual IEEE Conference on},
volume = {0},
year = {2004},
issn = {1093-0159},
pages = {82-90},
doi = {http://doi.ieeecomputersociety.org/10.1109/CCC.2004.1313805},
publisher = {IEEE Computer Society},
address = {Los Alamitos, CA, USA},
}
 
 
RefWorks Procite/RefMan/Endnote
x 
 
TY - CONF
JO - Computational Complexity, Annual IEEE Conference on
TI - Polylogarithmic-Round Interactive Proofs for coNP Collapse the Exponential Hierarchy
SN - 1093-0159
SP82
EP90
A1 - Alan L. Selman,
A1 - Samik Sengupta,
PY - 2004
KW - null
VL - 0
JA - Computational Complexity, Annual IEEE Conference on
ER -
 
Alan L. Selman, University at Buffalo
Samik Sengupta, University at Buffalo

It is known [BHZ87] that if every language in coNP has a constant-round interactive proof system, then the polynomial hierarchy collapses. On the other hand, Lund et al. [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 [Yap83], and improve upon an exponential version of the Karp-Lipton theorem [KL80], obtained first by Buhrman and Homer [BH92].

Citation:
Alan L. Selman, Samik Sengupta, "Polylogarithmic-Round Interactive Proofs for coNP Collapse the Exponential Hierarchy," ccc, pp.82-90, 19th Annual IEEE Conference on Computational Complexity (CCC'04), 2004
Usage of this product signifies your acceptance of the Terms of Use.