Stephen Cook
Stephen Cook | |
---|---|
Awards |
|
Scientific career | |
Fields | Arvind Gupta Anna Lubiw |
Stephen Arthur Cook OC OOnt (born December 14, 1939) is an American-Canadian computer scientist and mathematician who has made significant contributions to the fields of complexity theory and proof complexity. He is a university professor emeritus at the University of Toronto, Department of Computer Science and Department of Mathematics.
He is considered one of the forefathers of computational complexity theory.
Biography
Cook received his
Research
During his PhD, Cook worked on complexity of functions, mainly on multiplication. In his seminal 1971 paper "The Complexity of Theorem Proving Procedures",
Cook conjectures that there are optimization problems (with easily checkable solutions) that cannot be solved by efficient algorithms, i.e., P is not equal to NP. This conjecture has generated a great deal of research in computational complexity theory, which has considerably improved our understanding of the inherent difficulty of computational problems and what can be computed efficiently. Yet, the conjecture remains open and is among the seven famous Millennium Prize Problems.[5][6]
In 1982, Cook received the Turing Award for his contributions to complexity theory. His citation reads:
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 NP-complete class of problems has been one of the most active and important research activities in computer science for the last decade.
In his "Feasibly Constructive Proofs and the Propositional Calculus"
His main research areas are
Some other contributions
He named the complexity class NC after Nick Pippenger. The complexity class SC is named after him.[10] The definition of the complexity class AC0 and its hierarchy AC are also introduced by him.[11]
According to
Awards and honors
Cook was awarded an
Cook won the ACM Turing Award in 1982. Association for Computing Machinery honored him as a Fellow of ACM in 2008 for his fundamental contributions to the theory of computational complexity.[14] He was selected by the Association for Symbolic Logic to give the Gödel Lecture in 1999.[15]
The
Cook was granted the BBVA Foundation Frontiers of Knowledge Award 2015 in the Information and Communication Technologies category "for his important role in identifying what computers can and cannot solve efficiently," in the words of the jury's citation. His work, it continues, "has had a dramatic impact in all fields where complex computations are crucial."
Cook has supervised numerous MSc students, and 36 PhD students have completed their degrees under his supervision.[1]
Personal life
Cook lives with his wife in Toronto. They have two sons, one of whom is Olympic sailor Gordon Cook.[20]
See also
References
- ^ a b Stephen Cook at the Mathematics Genealogy Project
- ^ Kapron, Bruce. "Stephen Arthur Cook". A. M. Turing Award. Retrieved October 23, 2018.
- Richard Karp (2003). "A Personal View of Computer Science at Berkeley". University of California Berkeley. Retrieved February 12, 2023.
- ^ Stephen Cook (1971), The Complexity of Theorem Proving Procedures (PDF) – via University of TorontoStephen A. Cook (2009) [1971]. "The Complexity of Theorem-Proving Procedures". Retrieved February 12, 2023.
- ^ P vs. NP Archived October 14, 2013, at the Wayback Machine problem on Millennium Prize Problems page – Clay Mathematics Institute
- ^ P vs. NP Archived September 27, 2007, at the Wayback Machine problem's official description by Stephen Cook on Millennium Prize Problems
- S2CID 13309619.
- S2CID 2187041.
- ^ "Logical Foundations of Proof Complexity"'s official page
- ^ ""Steve's class": origin of SC". Theoretical Computer Science – Stack Exchange.
- ^ "Who introduced the complexity class AC?". Theoretical Computer Science – Stack Exchange.
- ^ "Twenty Questions for Donald Knuth".
- ^ "Awarded The Bernard Bolzano Honorary Medals for Merit in the Mathematical Sciences". Medals of the CAS. Czech Academy of Sciences. Retrieved April 13, 2024.
- ^ Association for Computing Machinery. "Stephen A Cook". awards.acm.org. Retrieved February 12, 2023.
- ^ "Gödel Lecturers – Association for Symbolic Logic". Retrieved November 8, 2021.
- ^ "25 Appointees Named to Ontario's Highest Honour". Ministry of Citizenship and Immigration.
- ^ Emily, Chung (February 27, 2013). "Computer scientist wins Canada's top science prize". cbc.ca. Retrieved February 27, 2013.
- ^ "Current Winner – 2012 – Stephen Cook". June 28, 2016.
- ^ "SaltWire | Halifax". www.saltwire.com. Retrieved February 12, 2023.
- ^ "Stephen A. Cook – Home Page".
External links
- Home page of Stephen A. Cook
- 'P versus NP' and the Limits of Computation – Public lecture given by Stephen Cook at the University of Toronto
- Oral history interview with Stephen Cook at Charles Babbage Institute, University of Minnesota. Cook discussed his education at the University of Michigan and Harvard University and early work at the University of California, Berkeley, and his growing interest in problems of computational complexity. Cook recounted his move to the University of Toronto in 1970 and the reception of his work on NP-completeness, leading up to his A.M. Turing Award.
- Stephen Arthur Cook at the Mathematics Genealogy Project
- Stephen A. Cook at DBLP Bibliography Server