Proving SAT does not have Small Circuits with an Application to the Two

	This Article
	Subscribers, please Login Purchase article: $19 PDF IEEE Xplore Subscribers RSS feed
	Share
	Email this Article to a friend
	Bibliographic References
	ASCII Text BibTex RefWorks Procite/RefMan/Endnote
	Add to:
	Digg Furl Spurl Blink Simpy Google Del.icio.us Y!MyWeb
	Search
	Similar Articles Articles by Lance Fortnow Articles by A. Pavan Articles by Samik Sengupta

18th Annual IEEE Conference on Computational Complexity (CCC'03)

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 -

Lance Fortnow

A. Pavan

Samik Sengupta

DOI Bookmark: http://doi.ieeecomputersociety.org/10.1109/CCC.2003.1214433

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

Peer Review Notice | Give Us Feedback

Usage of this product signifies your acceptance of the Terms of Use.