Propositional proof systems, the consistency of first order theories and the complexity of computations
Journal of Symbolic Logic 54 (3):1063-1079 (1989)
Abstract
We consider the problem about the length of proofs of the sentences $\operatorname{Con}_S(\underline{n})$ saying that there is no proof of contradiction in S whose length is ≤ n. We show the relation of this problem to some problems about propositional proof systemsAuthor's Profile
DOI
10.2307/2274765
Links
PhilArchive
External links
(no proxy)
Setup an account with your affiliations in order to access resources via your University's proxy server
Through your library
- Sign in / register and customize your OpenURL resolver
- Configure custom resolver
My notes
Similar books and articles
Structured Pigeonhole Principle, Search Problems and Hard Tautologies.Jan Krajíček - 2005 - Journal of Symbolic Logic 70 (2):619 - 630.
Bounded Arithmetic, Propositional Logic and Complexity Theory.Jan Krajíček - 1995 - Cambridge University Press.
Minimum propositional proof length is NP-Hard to linearly approximate.Michael Alekhnovich, Sam Buss, Shlomo Moran & Toniann Pitassi - 2001 - Journal of Symbolic Logic 66 (1):171-191.
The deduction rule and linear and near-linear proof simulations.Maria Luisa Bonet & Samuel R. Buss - 1993 - Journal of Symbolic Logic 58 (2):688-709.
Propositional Proof Systems and Fast Consistency Provers.Joost J. Joosten - 2007 - Notre Dame Journal of Formal Logic 48 (3):381-398.
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.
The complexity of propositional proofs.Nathan Segerlind - 2007 - Bulletin of Symbolic Logic 13 (4):417-481.
Analytics
Added to PP
2009-01-28
Downloads
23 (#501,637)
6 months
1 (#448,551)
2009-01-28
Downloads
23 (#501,637)
6 months
1 (#448,551)
Historical graph of downloads
Author's Profile
Citations of this work
Incompleteness in the finite domain.Pavel Pudlák - 2017 - Bulletin of Symbolic Logic 23 (4):405-441.
Functional interpretations of feasibly constructive arithmetic.Stephen Cook & Alasdair Urquhart - 1993 - Annals of Pure and Applied Logic 63 (2):103-200.
The complexity of propositional proofs.Nathan Segerlind - 2007 - Bulletin of Symbolic Logic 13 (4):417-481.
Propositional consistency proofs.Samuel R. Buss - 1991 - Annals of Pure and Applied Logic 52 (1-2):3-29.
The complexity of propositional proofs.Alasdair Urquhart - 1995 - Bulletin of Symbolic Logic 1 (4):425-467.
References found in this work
On the scheme of induction for bounded arithmetic formulas.A. J. Wilkie & J. B. Paris - 1987 - Annals of Pure and Applied Logic 35 (C):261-302.
