DocumentCode
1683512
Title
Proving SAT does not have small circuits with an application to the two queries problem
Author
Fortnow, Lance ; Pavan, A. ; Sengupta, Samik
Author_Institution
NEC Labs., Princeton, NJ, USA
fYear
2003
Firstpage
347
Lastpage
350
Abstract
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 PNP[1]=PNP[2], then the polynomial-time hierarchy collapses to S2P⊆Σ2p∩Π2p. Even showing that the hierarchy collapsed to Σ2p remained open.
Keywords
circuit complexity; computability; formal languages; probability; set theory; theorem proving; SAT; polynomial-time hierarchy; polynomial-time prover; probability; satisfiability; small circuit; two queries problem; Application software; Circuits; Computational complexity; Computer science; National electric code; Polynomials; Power engineering computing; Turing machines;
fLanguage
English
Publisher
ieee
Conference_Titel
Computational Complexity, 2003. Proceedings. 18th IEEE Annual Conference on
ISSN
1093-0159
Print_ISBN
0-7695-1879-6
Type
conf
DOI
10.1109/CCC.2003.1214433
Filename
1214433
Link To Document