Stephen Arthur Cook, OC, OOnt (born December 14, 1939) is an
American-Canadian computer scientist and mathematician who has made
major contributions to the fields of complexity theory and proof
complexity. He is currently a university professor at the University
of Toronto, Department of
Contents 1 Biography 2 Research 2.1 Some other contributions 3 Awards and honors 4 Personal life 5 See also 6 References 7 External links Biography[edit]
Cook received his
For his advancement of our understanding of the complexity of
computation in a significant and profound way. His seminal paper, The
Complexity of Theorem Proving Procedures, presented at the 1971 ACM
SIGACT Symposium on the Theory of Computing, laid the foundations for
the theory of NP-Completeness. The ensuing exploration of the
boundaries and nature of
In his "Feasibly Constructive Proofs and the Propositional
Calculus"[7] paper published in 1975, he introduced the equational
theory PV (standing for Polynomial-time Verifiable) to formalize the
notion of proofs using only polynomial-time concepts. He made another
major contribution to the field in his 1979 paper, joint with his
student Robert A. Reckhow, "The Relative Efficiency of Propositional
Proof Systems",[8] in which they formalized the notions of
p-simulation and efficient propositional proof system, which started
an area now called propositional proof complexity. They proved that
the existence of a proof system in which every true formula has a
short proof is equivalent to NP = coNP. Cook co-authored a book with
his student Phuong The Nguyen in this area titled "Logical Foundations
of Proof Complexity".[9]
His main research areas are complexity theory and proof complexity,
with excursions into programming language semantics, parallel
computation, and artificial intelligence. Other areas which he has
contributed to include bounded arithmetic, bounded reverse
mathematics, complexity of higher type functions, complexity of
analysis, and lower bounds in propositional proof systems.
Some other contributions[edit]
He named the complexity class NC after Nick Pippenger. The complexity
class SC is named after him.[10] The definition of the complexity
class
Professors Stephen A. Cook (right) with his friend Prof. Jan Krajíček (left) at the Fall school of Logic & Complexity in Prague, September 24, 2008 See also[edit] List of pioneers in computer science References[edit] ^ Stephen A. Cook,
External links[edit] Home page of Stephen A. Cook
‘P versus NP’ and the Limits of Computation - Public lecture given
by
v t e Fellows of the
Fellows Colin Atkinson David Barker Jean Beggs Harshad Bhadeshia David Keith Bowen Roger Cashmore Andrew Casson Thomas Cavalier-Smith David W. Clarke Enrico Coen Stephen Cook Peter Crane Richard Denton Raymond Dwek Charles Ellington Richard B. Flavell Ken Freeman Brian Greenwood J. Philip Grime David Hanna Geoffrey Hinton Steven Martin Raghunath Anant Mashelkar Yoshio Masui Ronald Charles Newman Mark Pepys Trevor Charles Platt Alan Plumb Richard J. Puddephatt Philip Ruffles Anthony Segal Ashoke Sen Jonathan Sprent James Staunton John Michael Taylor Robert K. Thomas Cheryll Tickle S. R. Srinivasa Varadhan Bernard Wood Brian S. Worthington Foreign John E. Casida Elias James Corey Walter Kohn Oliver Smithies Rolf M. Zinkernagel v t e A. M.
1960s
1970s
1980s
1990s
2000s
2010s Leslie G. Valiant (2010)
Authority control WorldCat Identities VIAF: 38354675 LCCN: nr2003030022 ISNI: 0000 0000 8220 6950 GND: 140808973 SUDOC: 074089021 MGP: 14011 DBLP: c/StephenACook A |