The Complexity of Propositional Proofs
- 1 December 2007
- journal article
- Published by Cambridge University Press (CUP) in The Bulletin of Symbolic Logic
- Vol. 13 (4) , 417-481
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
This publication has 104 references indexed in Scilit:
- Resolution cannot polynomially simulate compressed-BFSAnnals of Mathematics and Artificial Intelligence, 2005
- Exponential separation between Res(k) and Res(k+1) for k⩽ɛlognInformation Processing Letters, 2005
- Near Optimal Separation Of Tree-Like And General ResolutionCombinatorica, 2004
- Regular Resolution Lower Bounds For The Weak Pigeonhole PrincipleCombinatorica, 2004
- A sharp threshold in proof complexity yields lower bounds for satisfiability searchJournal of Computer and System Sciences, 2004
- Resolution lower bounds for the weak functional pigeonhole principleTheoretical Computer Science, 2003
- Linear Gaps between Degrees for the Polynomial Calculus Modulo Distinct PrimesJournal of Computer and System Sciences, 2001
- Proof complexity in algebraic systems and bounded depth Frege systems with modular countingcomputational complexity, 1996
- The complexity of the Pigeonhole PrincipleCombinatorica, 1994
- Exponential lower bounds for the pigeonhole principlecomputational complexity, 1993