A.M. TURING CENTENARY CELEBRATION WEBCAST
  • go to Kristen Nygaard 's profile page
  • go to Alan Kay's profile page
  • go to John McCarthy's profile page
  • go to Whitfield Diffie 's profile page
  • go to Marvin Minsky 's profile page
  • go to Silvio Micali's profile page
  • go to Kenneth E. Iverson 's profile page
  • go to Alfred V Aho's profile page
  • go to Yoshua Bengio's profile page
  • go to Maurice V. Wilkes's profile page
  • go to Raj Reddy's profile page
  • go to Edwin Catmull's profile page
  • go to Edward A Feigenbaum's profile page
  • go to Peter Naur's profile page
  • go to Donald E. Knuth's profile page
  • go to David Patterson's profile page
  • go to Niklaus E. Wirth's profile page
  • go to Dr. Jack Dongarra's profile page
  • go to Shafi Goldwasser 's profile page
  • go to Fernando Corbato's profile page
  • go to Andrew C Yao's profile page
  • go to Robert Melancton Metcalfe's profile page
  • go to Adi Shamir's profile page
  • go to Jeffrey D Ullman's profile page
A.M. TURING AWARD WINNERS BY...
Stephen A Cook

PHOTOGRAPHS

Stephen Arthur Cook DL Author Profile link

Canada – 1982
Short Annotated Bibliography
  1. Cook, Stephen A., “The complexity of theorem-proving procedures,” Proceedings of the 3rd Annual ACM Symposium on Theory of Computing (STOC '71), ACM, New York, NY, USA, 1971, pp. 151-158.  This seminal paper introduces the notion of NP-completeness, and presents a canonical NP-complete problem, the satisfiability problem for Boolean formulas (SAT). It also demonstrates how the technique of resource-bounded reductions can be used to show that problems are NP-complete.
  2. Cook, Stephen A. and Robert A. Reckhow, “The relative efficiency of propositional proof systems,” The Journal of Symbolic Logic, Volume 44, Number 1, 1979, pp. 36-50.  
  3. Cook, Stephen A., “Feasibly constructive proofs and the propositional calculus (Preliminary Version),” Proceedings of 7th Annual ACM Symposium on Theory of Computing (STOC '75), ACM, New York, NY, USA, 83-97.  These two papers initiate the study of two areas on the boundary of computational complexity and mathematical logic. The first paper proposes proof length as a measure of complexity for propositional proof systems, and proves that the existence of an efficient proof system for propositional tautologies is equivalent to the closure of the class NP under complementation. The second introduces a system PV for equational reasoning about poly-time concepts. It is shown that statements which are provable in PV have propositional translations with short proofs.
  4. Cook, Stephen A., “Soundness and completeness of an axiom system for program verification,” SIAM Journal on Computing, Volume 7, Number 1, 1978, pp. 70-90.  This paper presents a variant of Hoare logic for an ALGOL-like language which is sound and complete with respect to certain interpretations. Cook’s notion of relative completeness had a significant impact, and initiated a new line of study in programming language semantics.
  5. Cook, Stephen A., “A taxonomy of problems with fast parallel algorithms,” Information and Control, Volume 64, Issues 1-3, 1985, pp. 2-22.
  6. Beame, Paul W., Stephen A. Cook and H. James Hoover, “Log depth circuits for division and related problems,” SIAM Journal on Computing, Volume 15, Number 4, 1986, pp. 994-1003.  These two papers are representative of Cook’s contribution to the area of parallel algorithms and complexity. Cook was instrumental in formulating models of parallel computation, and in initiating the study parallel complexity and efficient parallel algorithms.
  7. Cook, Stephen A., “Characterizations of Pushdown Machines in Terms of Time-Bounded Computers,” Journal of the ACM, Volume 18, Number 1, 1971, pp. 4-18.  Introduces the class of auxiliary push-down automata, and uses this model to give characterizations the power of various known classes of push-down automata in terms of tape-bounded Turing machines.