The complexity of propositional proofs

Bulletin of Symbolic Logic 1 (4):425-467 (1995)
  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

Categories

Keywords

Reprint years

DOI

10.2307/421131

Links

PhilArchive



    Upload a copy of this work     Papers currently archived: 93,891

External links

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

Through your library

My notes

Similar books and articles

The complexity of propositional proofs.Nathan Segerlind - 2007 - Bulletin of Symbolic Logic 13 (4):417-481.
The Complexity of Propositional Proofs.Nathan Segerlind - 1995 - Bulletin of Symbolic Logic 1 (4):425-467.
The Complexity of Propositional Proofs with the Substitution Rule.Alasdair Urquhart - 2005 - Logic Journal of the IGPL 13 (3):287-291.
x1. Introduction. The classical propositional calculus has an undeserved reputation among logicians as being essentially trivial. I hope to convince the reader that it presents some of the most challenging and intriguing problems in modern logic. Although the problem of the complexity of propositional proofs is very. [REVIEW]Alasdair Urquhart - 1995 - Bulletin of Symbolic Logic 1 (4):425-467.
reputation among logicians as being essentially trivial. I hope to convince the reader that it presents some of the most challenging and intriguing problems in modern logic. Although the problem of the complexity of propositional proofs is very natural, it has been investigated systematically only since the late 1960s. [REVIEW]Alasdair Urquhart - 1995 - Bulletin of Symbolic Logic 1 (4):425-467.
Reflections on Proof Complexity and Counting Principles.Noah Fleming & Toniann Pitassi - 2021 - In Ivo Düntsch & Edwin Mares (eds.), Alasdair Urquhart on Nonclassical and Algebraic Logic and Complexity of Proofs. Springer Verlag. pp. 497-520.
Substitution and Propositional Proof Complexity.Sam Buss - 2021 - In Ivo Düntsch & Edwin Mares (eds.), Alasdair Urquhart on Nonclassical and Algebraic Logic and Complexity of Proofs. Springer Verlag. pp. 477-496.
Bounded arithmetic, propositional logic, and complexity theory.Jan Krajíček - 1995 - New York, NY, USA: Cambridge University Press.
Simplified Lower Bounds for Propositional Proofs.Alasdair Urquhart & Xudong Fu - 1996 - Notre Dame Journal of Formal Logic 37 (4):523-544.
On meta complexity of propositional formulas and propositional proofs.Pavel Naumov - 2008 - Archive for Mathematical Logic 47 (1):35-52.

Analytics

Added to PP
2009-01-28

Downloads
136 (#135,025)

6 months
15 (#234,431)

Historical graph of downloads
How can I increase my downloads?

Author's Profile

Alasdair Urquhart
University of Toronto, St. George Campus

Citations of this work

Non-transitive Correspondence Analysis.Yaroslav Petrukhin & Vasily Shangin - 2023 - Journal of Logic, Language and Information 32 (2):247-273.
The proof complexity of linear algebra.Michael Soltys & Stephen Cook - 2004 - Annals of Pure and Applied Logic 130 (1-3):277-323.
The Depth of Resolution Proofs.Alasdair Urquhart - 2011 - Studia Logica 99 (1-3):349-364.

View all 6 citations / Add more citations

References found in this work

Introduction to mathematical logic.Alonso Church - 1958 - Revue de Métaphysique et de Morale 63 (1):118-118.
Existence and feasibility in arithmetic.Rohit Parikh - 1971 - Journal of Symbolic Logic 36 (3):494-508.

View all 15 references / Add more references