The Complexity of Propositional Proofs

Bulletin of Symbolic Logic 1 (4):425-467 (1995)
  Copy   BIBTEX

Abstract

This article has no associated abstract. (fix it)

Categories

Keywords

Reprint years

DOI

10.2178/bsl/1203350879

Links

PhilArchive



    Upload a copy of this work     Papers currently archived: 91,610

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.Alasdair Urquhart - 1995 - Bulletin of Symbolic Logic 1 (4):425-467.
On meta complexity of propositional formulas and propositional proofs.Pavel Naumov - 2008 - Archive for Mathematical Logic 47 (1):35-52.
The complexity of propositional proofs.Nathan Segerlind - 2007 - Bulletin of Symbolic Logic 13 (4):417-481.
The Complexity of Propositional Proofs with the Substitution Rule.Alasdair Urquhart - 2005 - Logic Journal of the IGPL 13 (3):287-291.
Bounded arithmetic, propositional logic, and complexity theory.Jan Krajíček - 1995 - New York, NY, USA: Cambridge University Press.
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.
The Depth of Resolution Proofs.Alasdair Urquhart - 2011 - Studia Logica 99 (1-3):349-364.
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.
Simplified Lower Bounds for Propositional Proofs.Alasdair Urquhart & Xudong Fu - 1996 - Notre Dame Journal of Formal Logic 37 (4):523-544.
On the computational content of intuitionistic propositional proofs.Samuel R. Buss & Pavel Pudlák - 2001 - Annals of Pure and Applied Logic 109 (1-2):49-64.
Polynomial size proofs of the propositional pigeonhole principle.Samuel R. Buss - 1987 - Journal of Symbolic Logic 52 (4):916-927.
The three dimensions of proofs.Yves Guiraud - 2006 - Annals of Pure and Applied Logic 141 (1):266-295.
Propositional consistency proofs.Samuel R. Buss - 1991 - Annals of Pure and Applied Logic 52 (1-2):3-29.
String Rewriting and Proof Complexity: an interpretation of Resolution.Stefano Cavagnetto - 2009 - Reports on Mathematical Logic:167-200.
The proof complexity of linear algebra.Michael Soltys & Stephen Cook - 2004 - Annals of Pure and Applied Logic 130 (1-3):277-323.

Analytics

Added to PP
2017-02-22

Downloads
9 (#1,247,499)

6 months
4 (#776,340)

Historical graph of downloads
How can I increase my downloads?

Citations of this work

EXPtime tableaux for ALC.Francesco M. Donini & Fabio Massacci - 2000 - Artificial Intelligence 124 (1):87-138.

View all 15 citations / Add more citations

References found in this work

No references found.

Add more references