Logical foundations of proof complexity

&
Bulletin of Symbolic Logic 17 (3):462-464 (2011)
  Copy   BIBTEX

Abstract

This article has no associated abstract. (fix it)

Categories

Keywords

Reprint years

DOI

10.2178/bsl/1309952322

Other Versions

No versions found

Links

PhilArchive



    Upload a copy of this work     Papers currently archived: 100,874

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

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.
Stephen Bellantoni and Stephen Cook. A new recursion-theoretic characterization of the polytime functions. Computational complexity, vol. 2 , pp. 97–110. - Arnold Beckmann and Andreas Weiermann. A term rewriting characterization of the polytime functions and related complexity classes. Archive for mathematical logic, vol. 36 , pp. 11–30. [REVIEW]Karl-Heinz Niggl - 2000 - Bulletin of Symbolic Logic 6 (3):351-353.
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.
Lowerbounds in Proof Complexity.J. J. Joosten - 2007 - Bulletin of Symbolic Logic 13 (2):263-263.
Proof Theory and Logical Complexity.Helmut Pfeifer & Jean-Yves Girard - 1989 - Journal of Symbolic Logic 54 (4):1493.
REVIEWS-A first course in logic: An introduction to model theory, proof theory, computability, and complexity.S. Hedman & Alasdair Urquhart - 2007 - Bulletin of Symbolic Logic 13 (4):538-539.
Modal logics K, T, K4, S4: Labelled proof systems and new complexity results.David Basin, Sean Matthews & Luca Vigano - 1999 - Bulletin of Symbolic Logic 5 (1):91-93.
Gödel '96 Logical Foundations of Mathematics, Computer Science and Physics Kurt GÖdel's Legacy.Petr Hájek & Jiří Zlatuška - 1996 - Bulletin of Symbolic Logic 2 (4):473-473.
Jan Krajìček, Proof Complexity, Encyclopedia of Mathematics and Its Applications, no. 170, Cambridge University Press, Cambridge, UK, 2019, xvi + 516 pp. [REVIEW]Moritz Müller - 2023 - Bulletin of Symbolic Logic 29 (2):296-297.
Jean-Yves Girard. Proof theory and logical complexity. Volume I. Studies in proof theory, no. 1. Bibliopolis, Naples 1987, also distributed by Humanities Press, Atlantic Highlands, N.J., 503 pp. [REVIEW]Helmut Pfeiffer - 1989 - Journal of Symbolic Logic 54 (4):1493-1494.

Analytics

Added to PP
2017-02-21

Downloads
15 (#1,213,741)

6 months
5 (#1,002,523)

Historical graph of downloads
How can I increase my downloads?

Author's Profile

Phuong Tu Nguyen
University College London

Citations of this work

Justification as ignorance and logical omniscience.Daniel Waxman - 2022 - Asian Journal of Philosophy 1 (1):1-8.
Strict Finitism, Feasibility, and the Sorites.Walter Dean - 2018 - Review of Symbolic Logic 11 (2):295-346.
Open induction in a bounded arithmetic for TC0.Emil Jeřábek - 2015 - Archive for Mathematical Logic 54 (3-4):359-394.
Short propositional refutations for dense random 3CNF formulas.Sebastian Müller & Iddo Tzameret - 2014 - Annals of Pure and Applied Logic 165 (12):1864-1918.

View all 14 citations / Add more citations

References found in this work

No references found.

Add more references