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

Other Versions

No versions found

Links

PhilArchive



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

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.
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. Diskussion zur Grundlegung der Mathematik . A reprint of 4184. Collected Works, Volume I, Publications 1929– 1936, 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, pp. 200, 202. - Kurt Gödel. Discussion on providing a foundation for mathematics . English translation by John Dawson of the preceding. Collected Works, Volume I, Publications 1929– 1936, 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, pp. 201, 203. , pp. 125-126.) - Kurt Gödel. Nachtrag. A reprint of 4185. Collected Works, Volume I, Publications 1929– 1936, by Kurt Gödel, edited by Solomon Feferman, John W. DawsonJr., Stephen C. Kleene, Gregory H. Moore, Robert M. Solovay, and Jean van Heijenoor. [REVIEW]Martin Davis - 1990 - Journal of Symbolic Logic 55 (1):343-343.

Analytics

Added to PP
2024-05-27

Downloads
19 (#1,074,273)

6 months
12 (#294,748)

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