The relative efficiency of propositional proof systems
Journal of Symbolic Logic 44 (1):36-50 (1979)
Abstract
This article has no associated abstract. (fix it)DOI
10.2307/2273702
My notes
Similar books and articles
Indexed systems of sequents and cut-elimination.Grigori Mints - 1997 - Journal of Philosophical Logic 26 (6):671-696.
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.
Polynomial size proofs of the propositional pigeonhole principle.Samuel R. Buss - 1987 - Journal of Symbolic Logic 52 (4):916-927.
The complexity of propositional proofs.Nathan Segerlind - 2007 - Bulletin of Symbolic Logic 13 (4):417-481.
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.
Bounded Arithmetic, Propositional Logic and Complexity Theory.Jan Krajíček - 1995 - Cambridge University Press.
Decomposition proof systems for gödel-Dummett logics.Arnon Avron & Beata Konikowska - 2001 - Studia Logica 69 (2):197-219.
Propositional proof systems, the consistency of first order theories and the complexity of computations.Jan Krajíček & Pavel Pudlák - 1989 - Journal of Symbolic Logic 54 (3):1063-1079.
Analytics
Added to PP
2009-01-28
Downloads
102 (#123,290)
6 months
2 (#299,675)
2009-01-28
Downloads
102 (#123,290)
6 months
2 (#299,675)
Historical graph of downloads
Citations of this work
Computational properties of argument systems satisfying graph-theoretic constraints.Paul E. Dunne - 2007 - Artificial Intelligence 171 (10-15):701-729.
Audiences in argumentation frameworks.Trevor J. M. Bench-Capon, Sylvie Doutre & Paul E. Dunne - 2007 - Artificial Intelligence 171 (1):42-71.
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.
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.
References found in this work
Natural Deduction: A Proof-Theoretical Study.Richmond Thomason - 1965 - Journal of Symbolic Logic 32 (2):255-256.