loading...
 This Article 
   
 Share 
   
 Bibliographic References 
   
 Add to: 
 
Digg
Furl
Spurl
Blink
Simpy
Google
Del.icio.us
Y!MyWeb
 
 Search 
   
18th Annual IEEE Conference on Computational Complexity (CCC'03)
Proving SAT does not have Small Circuits with an Application to the Two
Aarhus, Denmark
July 07-July 10
ISBN: 0-7695-1879-6
ASCII Text
x 
 
Lance Fortnow, A. Pavan, Samik Sengupta, "Proving SAT does not have Small Circuits with an Application to the Two," Computational Complexity, Annual IEEE Conference on, pp. 347, 18th Annual IEEE Conference on Computational Complexity (CCC'03), 2003.
 
 
BibTex
x
 
@article{ 10.1109/CCC.2003.1214433,
author = {Lance Fortnow and A. Pavan and Samik Sengupta},
title = {Proving SAT does not have Small Circuits with an Application to the Two},
journal ={Computational Complexity, Annual IEEE Conference on},
volume = {0},
year = {2003},
issn = {1093-0159},
pages = {347},
doi = {http://doi.ieeecomputersociety.org/10.1109/CCC.2003.1214433},
publisher = {IEEE Computer Society},
address = {Los Alamitos, CA, USA},
}
 
 
RefWorks Procite/RefMan/Endnote
x 
 
TY - CONF
JO - Computational Complexity, Annual IEEE Conference on
TI - Proving SAT does not have Small Circuits with an Application to the Two
SN - 1093-0159
SP
EP
A1 - Lance Fortnow,
A1 - A. Pavan,
A1 - Samik Sengupta,
PY - 2003
KW - null
VL - 0
JA - Computational Complexity, Annual IEEE Conference on
ER -
 
We show that if SAT does not have small circuits, then there must exist a small number of formulas such that every small circuit fails to compute satisfiability correctly on at least one of these formulas. We use this result to show that if P_{}^{NP} [1] = P_{}^{NP[2]}, then the polynomial-time hierarchy collapses to S_2^P \subseteq \sum {} _2^P \cap \prod {} _2^P Even showing that the hierarchy collapsed to \sum {} _2^P remained open prior to this paper.
Citation:
Lance Fortnow, A. Pavan, Samik Sengupta, "Proving SAT does not have Small Circuits with an Application to the Two," ccc, pp.347, 18th Annual IEEE Conference on Computational Complexity (CCC'03), 2003
Usage of this product signifies your acceptance of the Terms of Use.