The complexity of propositional proofs

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

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

Links

PhilArchive



    Upload a copy of this work     Papers currently archived: 92,323

External links

Setup an account with your affiliations in order to access resources via your University's proxy server

Through your library

Similar books and articles

Implicit Proofs.Jan Krajíček - 2004 - Journal of Symbolic Logic 69 (2):387 - 397.
Socratic proofs.Andrzej Wiśniewski - 2004 - Journal of Philosophical Logic 33 (3):299-326.
The complexity of propositional proofs.Alasdair Urquhart - 1995 - Bulletin of Symbolic Logic 1 (4):425-467.
Bounded arithmetic, propositional logic, and complexity theory.Jan Krajíček - 1995 - New York, NY, USA: Cambridge University Press.

Analytics

Added to PP
2009-02-05

Downloads
71 (#232,616)

6 months
11 (#245,876)

Historical graph of downloads
How can I increase my downloads?