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 [Book Review]

Bulletin of Symbolic Logic 29 (4):657-660 (2023)
  Copy   BIBTEX

Abstract

This article has no associated abstract. (fix it)

Categories

Keywords

Reprint years

DOI

10.1017/bsl.2023.38

Links

PhilArchive



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

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 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.
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.
Wang Hao. Tag systems and lag systems. Mathematische Annalen, vol. 152 , pp. 65–74.Cocke John and Minsky Marvin. Universality of tag systems with D = 2. Journal of the Association for Computing Machinery, vol. 11 , pp. 15–20.Cook Stephen A.. The solvability of the derivability problem for one-normal systems. Journal of the Association for Computing Machinery, vol. 13 , pp. 223–225. [REVIEW]Ann Yasuhara - 1971 - Journal of Symbolic Logic 36 (2):344.
Stephen C. Kleene. Origins of recursive function theory. Annals of the history of computing, vol. 3 , pp. 52– 67. - Martin Davis. Why Gödel didn't have Church's thesis. Information and control, vol. 54 , pp. 3– 24. - Stephen C. Kleene. Reflections on Church's thesis. Notre Dame journal of formal logic, vol. 28 , pp. 490– 498. [REVIEW]Stewart Shapiro - 1990 - Journal of Symbolic Logic 55 (1):348-350.
S. A. Cook and Hao Wang. Characterizations of ordinal numbers in set theory. Mathematische Annalen, vol. 164 , pp. 1–25. [REVIEW]Azriel Lévy - 1968 - Journal of Symbolic Logic 33 (1):113.
Elementary arithmetic.Geoffrey E. Ostrin & Stanley S. Wainer - 2005 - Annals of Pure and Applied Logic 133 (1):275-292.
Harvey M. Friedman, Stephen G. Simpson, and Rick L. Smith. Countable algebra and set existence axioms. Annals of pure and applied logic, vol. 25 , pp. 141–181. - Harvey M. Friedman, Stephen G. Simpson, and Rick L. Smith. Addendum to “Countable algebra and set existence axioms.” Annals of pure and applied logic, vol. 28 , pp. 319–320. [REVIEW]Peter G. Clote - 1987 - Journal of Symbolic Logic 52 (1):276-278.
Albert Cook: The Odyssey by Homer. (A Norton Critical Edition.) Pp. xi + 516. New York: W. W. Norton, 1974. Paper, $2.45. [REVIEW]J. B. Hainsworth - 1978 - The Classical Review 28 (01):144-145.
Jan Krajíček, Pavel Pudlák, and Gaisi Takeuti. Bounded arithmetic and the polynomial hierarchy. Ibid., vol. 52 , pp. 143–153. - Samuel R. Buss. Relating the bounded arithmetic and polynomial time hierarchies. Ibid., vol. 75 , pp. 67–77. - Domenico Zambella. Notes on polynomially bounded arithmetic. The journal of symbolic logic, vol. 61 , pp. 942–966. [REVIEW]Stephen Cook - 1999 - Journal of Symbolic Logic 64 (4):1821-1823.
Kurt Gödel. Review of Hahn's Reelle Funktionen. by Kurt Gödel, edited by Solomon Feferman, John W. DawsonJr., Stephen C. Kleene, Gregory H. Moore, Robert M. Solovay, and Jean van Heijenoort, Clarendon Press, Oxford University Press, New York and Oxford1986, even pp. 332– 336. , Literaturberichte, pp. 20– 22.) - Kurt Gödel. English translation by John Dawson of this review. Reelle Funktionen, by Kurt Gödel, edited by Solomon Feferman, John W. DawsonJr., Stephen C. Kleene, Gregory H. Moore, Robert M. Solovay, and Jean van Heijenoort, Clarendon Press, Oxford University Press, New York and Oxford1986 odd pp. 333– 337. [REVIEW]Martin Davis - 1990 - Journal of Symbolic Logic 55 (1):346-347.

Analytics

Added to PP
2024-05-27

Downloads
6 (#711,559)

6 months
6 (#1,472,471)

Historical graph of downloads
How can I increase my downloads?

Author's Profile

Citations of this work

No citations found.

Add more citations

References found in this work

No references found.

Add more references