The relative efficiency of propositional proof systems

&
Journal of Symbolic Logic 44 (1):36-50 (1979)
  Copy   BIBTEX

Abstract

This article has no associated abstract. (fix it)

Categories

Keywords

Reprint years

DOI

10.2307/2273702

Links

PhilArchive



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

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

Relative efficiency of propositional proof systems: resolution vs. cut-free LK.Noriko H. Arai - 2000 - Annals of Pure and Applied Logic 104 (1-3):3-16.
Frege systems for extensible modal logics.Emil Jeřábek - 2006 - Annals of Pure and Applied Logic 142 (1):366-379.
Polynomial size proofs of the propositional pigeonhole principle.Samuel R. Buss - 1987 - Journal of Symbolic Logic 52 (4):916-927.
The Relative Efficiency of Propositional Proofs Systems for Classical and Nonclassical Propositional Logic.Anahit Chubaryan, Armine Chubaryan & Sergey Sayadyan - 2007 - In Jean-Yves Béziau & Alexandre Costa-Leite (eds.), Perspectives on Universal Logic. Milan, Italy: Polimetrica. pp. 265.
Stephen Cook and Phuong Nguyen. Logical foundations of proof complexity. Perspectives in Logic. Cambridge University Press, New York, 2010, 15 + 479 pp. [REVIEW]Albert Atserias - 2011 - Bulletin of Symbolic Logic 17 (3):462-464.
Logic, Automata, and Computational Complexity: The Works Of Stephen A. Cook_. Edited by Bruce M. Kapron, ACM Books, vol. 43. Association for Computing Machinery, New York, xxvi + 398 pp.—therein: - Michelle Waitzman. _Stephen Cook: Complexity’s Humble Hero_, pp. 3–28. - Bruce M. Kapron and Stephen A. Cook, _ACM Interview of Stephen A. Cook by Bruce M. Kapron_, pp. 29–44. - Stephen A. Cook, _Overview of Computational Complexity_, pp. 47–70. - Christos H. Papadimitriou, _Cook’s NP-Completeness Paper and the Dawn of the New Theory_, pp. 73–82. - Jan Krajíček, _The Cook–Reckhow Definition_, pp. 83–94. - Sam Buss, _Polynomially Verifiable Arithmetic_, pp. 95–106. - Paul Beame and Pierre McKenzie, _Towards a Complexity Theory of Parallel Computation_, pp. 107–126. - Nicholas Pippenger, _Computation with Limited Space_, pp. 127–140. - Stephen A. Cook, _The Complexity of Theorem-Proving Procedures_, pp. 143–152. - Stephen A. Cook, Characterizations of Pushdown Machines in Terms of Time-Bound. [REVIEW]Pavel Pudlák - 2023 - Bulletin of Symbolic Logic 29 (4):657-660.
Review: Hao Wang, Tag Systems and Lag Systems; John Cocke, Marvin Minsky, Universality of Tag Systems with $D = 2$; Stephen A. Cook, The Solvability of the Derivability Problem for One-Normal Systems. [REVIEW]Ann Yasuhara - 1971 - Journal of Symbolic Logic 36 (2):344-344.
Proof of the Axiomatizability of full Many-Valued Systems of Propositional Calculus.Jerzy Slupecki - 1946 - Journal of Symbolic Logic 11 (3):92-93.
Propositional consistency proofs.Samuel R. Buss - 1991 - Annals of Pure and Applied Logic 52 (1-2):3-29.
Review: Jerzy Slupecki, Proof of the Axiomatizability of full Many-Valued Systems of Propositional Calculus. [REVIEW]Henryk Stonert - 1946 - Journal of Symbolic Logic 11 (3):92-93.

Analytics

Added to PP
2009-01-28

Downloads
133 (#137,560)

6 months
27 (#136,197)

Historical graph of downloads
How can I increase my downloads?

Citations of this work

Informal proof, formal proof, formalism.Alan Weir - 2016 - Review of Symbolic Logic 9 (1):23-43.

View all 66 citations / Add more citations

References found in this work

Natural Deduction: A Proof-Theoretical Study.Richmond Thomason - 1965 - Journal of Symbolic Logic 32 (2):255-256.
Introduction to Mathematical Logic.S. C. Kleene - 1956 - Journal of Symbolic Logic 23 (3):362-362.

Add more references