Bulletin of Symbolic Logic 13 (4):417-481 (2007)

Abstract
Propositional proof complexity is the study of the sizes of propositional proofs, and more generally, the resources necessary to certify propositional tautologies. Questions about proof sizes have connections with computational complexity, theories of arithmetic, and satisfiability algorithms. This is article includes a broad survey of the field, and a technical exposition of some recently developed techniques for proving lower bounds on proof sizes
Keywords No keywords specified (fix it)
Categories (categorize this paper)
DOI 10.2178/bsl/1203350879
Options
Edit this record
Mark as duplicate
Export citation
Find it on Scholar
Request removal from index
Revision history

Download options

PhilArchive copy


Upload a copy of this paper     Check publisher's policy     Papers currently archived: 53,719
Through your library

References found in this work BETA

No references found.

Add more references

Citations of this work BETA

The Proof Complexity of Linear Algebra.Michael Soltys & Stephen Cook - 2004 - Annals of Pure and Applied Logic 130 (1-3):277-323.

View all 12 citations / Add more citations

Similar books and articles

Analytics

Added to PP index
2009-02-05

Total views
49 ( #195,809 of 2,349,718 )

Recent downloads (6 months)
1 ( #511,368 of 2,349,718 )

How can I increase my downloads?

Downloads

My notes