Bulletin of Symbolic Logic 13 (4):417-481 (2007)
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)|
References found in this work BETA
No references found.
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.
The Complexity of Analytic Tableaux.Noriko H. Arai, Toniann Pitassi & Alasdair Urquhart - 2006 - Journal of Symbolic Logic 71 (3):777 - 790.
Towards–Via Proof Complexity and Search.Samuel R. Buss - 2012 - Annals of Pure and Applied Logic 163 (7):906-917.
The Complexity of Resolution Refinements.Joshua Buresh-Oppenheim & Toniann Pitassi - 2007 - Journal of Symbolic Logic 72 (4):1336 - 1352.
Similar books and articles
The Complexity of Propositional Proofs.Alasdair Urquhart - 1995 - Bulletin of Symbolic Logic 1 (4):425-467.
Interpolation Theorems, Lower Bounds for Proof Systems, and Independence Results for Bounded Arithmetic.Jan Krajíček - 1997 - Journal of Symbolic Logic 62 (2):457-486.
Polynomial Size Proofs of the Propositional Pigeonhole Principle.Samuel R. Buss - 1987 - Journal of Symbolic Logic 52 (4):916-927.
Lower Bounds for Cutting Planes Proofs with Small Coefficients.Maria Bonet, Toniann Pitassi & Ran Raz - 1997 - Journal of Symbolic Logic 62 (3):708-728.
Propositional Proof Systems, the Consistency of First Order Theories and the Complexity of Computations.Jan Krajíček & Pavel Pudlák - 1989 - Journal of Symbolic Logic 54 (3):1063-1079.
Bounded Arithmetic, Propositional Logic, and Complexity Theory.Jan Krajíček - 1995 - Cambridge University Press.
Added to index2009-02-05
Total downloads30 ( #171,812 of 2,172,020 )
Recent downloads (6 months)1 ( #325,967 of 2,172,020 )
How can I increase my downloads?