default search action
Logic, Automata, and Computational Complexity 2023
- Bruce M. Kapron:
Logic, Automata, and Computational Complexity: The Works of Stephen A. Cook. ACM Books 43, ACM 2023, ISBN 979-8-4007-0779-7 - Bruce M. Kapron:
Introduction.
Biographical Background
- Michelle Waitzman:
Stephen Cook: Complexity's Humble Hero. 3-28 - ACM Interview of Stephen A. Cook by Bruce M. Kapron. 29-44
The Turing Award Lecture
- Stephen A. Cook:
The 1982 ACM Turing Award Lecture: An Overview of Computational Complexity. 47-70
Perspectives on Cook's Work
- Christos H. Papadimitriou:
Cook's NP-completeness Paper and the Dawn of the New Theory. 73-82 - Jan Krajícek:
The Cook-Reckhow Definition. 83-94 - Sam Buss:
Polynomially Verifiable Arithmetic. 95-106 - Paul Beame
, Pierre McKenzie:
Towards a Complexity Theory of Parallel Computation. 107-126 - Nicholas Pippenger:
Computation with Limited Space. 127-140
Selected Papers
- Stephen A. Cook:
The Complexity of Theorem-Proving Procedures. 143-152 - Stephen A. Cook:
Characterizations of Pushdown Machines in Terms of Time-Bounded Computers. 153-172 - Stephen A. Cook, Robert A. Reckhow:
The Relative Efficiency of Propositional Proof Systems. 173-192 - Stephen A. Cook:
Feasibly Constructive Proofs and the Propositional Calculus (Preliminary Version). 193-218 - Stephen A. Cook:
Towards a Complexity Theory of Synchronous Parallel Computation. 219-244 - Allan Borodin, Stephen A. Cook:
A Time-Space Tradeoff for Sorting on a General Sequential Model of Computation. 245-260 - Stephen A. Cook, Pierre McKenzie, Dustin Wehr, Mark Braverman, Rahul Santhanam:
Pebbles and Branching Programs for Tree Evaluation. 261-318
The Berkeley Notes
- Bruce M. Kapron:
Cook's Berkeley Notes. 321-324 - Stephen A. Cook:
A Survey of Classes of Primitive Recursive Functions. 325-336 - Further Reading. 337-338
- Bibliography. 339-382
- Contributors' Biographies/Index. 383-398
manage site settings
To protect your privacy, all features that rely on external API calls from your browser are turned off by default. You need to opt-in for them to become active. All settings here will be stored as cookies with your web browser. For more information see our F.A.Q.
last updated on 2025-11-11 22:58 CET by the dblp team
all metadata released as open data under CC0 1.0 license
see also: Terms of Use | Privacy Policy | Imprint
dblp was originally created in 1993 at:
since 2018, dblp has been operated and maintained by:
the dblp computer science bibliography is funded and supported by: