Editing Stephen Cook

{{Short description|American-Canadian computer scientist, contributor to complexity theory}}
{{distinguish|Steven Cook}}
{{Other people}}
{{Use mdy dates|date=February 2023}}
{{Infobox scientist
| name = Stephen Cook
| honorific_suffix  = {{Post-nominals|country=CAN|size=100%|sep=|OC|OOnt}}
| birth_name = Stephen Arthur Cook
| image = Prof.Cook.jpg
| image_upright = 
| caption = Cook in 2008
| birth_date = {{birth date and age|1939|12|14}}
| birth_place = [[Buffalo, New York|Buffalo]], New York
| death_date =
| death_place =
| residence =
| citizenship =
| nationality =
| ethnicity =
| field = [[Computer Science]]
| work_institution = [[University of Toronto]]<br>[[University of California, Berkeley]]
| education = [[University of Michigan]] ([[Bachelor of Arts|BA]])<br>[[Harvard University]] ([[Master of Arts|MA]], [[Doctor of Philosophy|PhD]])
| thesis_title =   On the Minimum Computation Time of Functions
| thesis_url  =         <!--(or  | thesis1_url  =   and  | thesis2_url  =  )-->
| thesis_year =   1966
| doctoral_advisor = [[Hao Wang (academic)|Hao Wang]]
| doctoral_students = [[Mark Braverman (mathematician)|Mark Braverman]]<ref name="mathgenealogy"/><br> [[Toniann Pitassi]] <br> [[Walter Savitch]] <br> [[Arvind Gupta (academic)|Arvind Gupta]] <br> [[Anna Lubiw]]
| known_for = [[NP-complete]]ness <br> Propositional [[proof complexity]] <br> [[Cook–Levin theorem]]
| author_abbreviation_bot =
| author_abbreviation_zoo =
| prizes =
{{plainlist|
* [[Turing Award]] {{small|(1982)}}
* [[Gödel Lecture]] {{small|(1999)}}
* [[CRM-Fields-PIMS prize]] {{small|(1999)}}
* [[John L. Synge Award]] {{small|(2006)}}
* [[Bernard Bolzano Medal]] {{small|(2008)}}
* [[Gerhard Herzberg Canada Gold Medal for Science and Engineering]] {{small|(2012)}}
* [[Order of Canada|Officer of Order of Canada]] {{small|(2015)}}
* [[BBVA Foundation Frontiers of Knowledge Award]] {{small|(2015)}}
}}
| religion =
| footnotes =
}}
'''Stephen Arthur Cook''' {{Post-nominals|country=CAN|size=100%|OC|OOnt}} (born December 14, 1939) is an American-Canadian [[computer scientist]] and mathematician who has made significant contributions to the fields of [[computational complexity theory|complexity theory]] and [[proof complexity]]. He is a university professor emeritus at the [[University of Toronto]], Department of Computer Science and [[University of Toronto Department of Mathematics|Department of Mathematics]].

He is considered one of the forefathers of [[computational complexity theory]].

==Biography==
[[File:Stephen A. Cook 1968 (enlarged portion).jpg|upright|thumb|Cook in 1968]]
Cook received his [[bachelor's degree]] in 1961 from the [[University of Michigan]], and his master's degree and PhD from [[Harvard University]], respectively in 1962 and 1966, from the Mathematics Department.<ref>{{cite web|url=https://amturing.acm.org/award_winners/cook_n991950.cfm|title=Stephen Arthur Cook|website=A. M. Turing Award|first=Bruce|last=Kapron|access-date=October 23, 2018}}</ref> He joined the [[University of California, Berkeley]], mathematics department in 1966 as an assistant professor, and stayed there until 1970 when he was denied reappointment. In a speech celebrating the 30th anniversary of the Berkeley electrical engineering and computer sciences department, fellow [[Turing Award]] winner and Berkeley professor [[Richard Karp]] said that, "It is to our everlasting shame that we were unable to persuade the math department to give him tenure."<ref>{{Cite web|title=A Personal View of Computer Science at Berkeley| date= 2003  | author1=Richard Karp| author-link= Richard Karp|url=https://www2.eecs.berkeley.edu/bears/CS_Anniversary/karp-talk.html|access-date=February 12, 2023|website=University of California Berkeley }}</ref> Cook joined the faculty of the [[University of Toronto]], Computer Science and Mathematics Departments in 1970 as an associate professor, where he was promoted to professor in 1975 and [[Distinguished Professor]] in 1985.

==Research==

During his PhD, Cook worked on complexity of functions, mainly on multiplication. In his seminal 1971 paper "The Complexity of Theorem Proving Procedures",<ref>{{ citation| url=http://www.cs.toronto.edu/~sacook/homepage/1971.pdf | title=The Complexity of Theorem Proving Procedures | date= 1971 | author1= Stephen Cook | via= University of Toronto}}{{pb}}{{Cite web|author1=Stephen A. Cook|title=The Complexity of Theorem-Proving Procedures|url=http://4mhz.de/cook.html|date=2009|orig-date=1971|access-date=February 12, 2023}}</ref> Cook formalized the notions of [[polynomial-time reduction]] (also known as [[Cook reduction]]) and [[NP-complete]]ness, and proved the existence of an [[NP-complete]] problem by showing that the [[Boolean satisfiability problem]] (usually known as SAT) is [[NP-complete]]. This theorem was proven independently by [[Leonid Levin]] in the [[Soviet Union]], and has thus been given the name [[Cook–Levin theorem|the Cook–Levin theorem]]. The paper also formulated the most famous problem in computer science, the [[P vs. NP problem]]. Informally, the "P vs. NP" question asks whether every optimization problem whose answers can be efficiently verified for correctness/optimality can be solved optimally with an efficient algorithm. Given the abundance of such optimization problems in everyday life, a positive answer to the "P vs. NP" question would likely have profound practical and philosophical consequences.

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]].<ref>[http://www.claymath.org/millennium/P_vs_NP/ P vs. NP] {{webarchive |url=https://web.archive.org/web/20131014194456/http://www.claymath.org/millennium/P_vs_NP/ |date=October 14, 2013 }} problem on [[Millennium Prize Problems]] page – [[Clay Mathematics Institute]]</ref><ref>[http://www.claymath.org/millennium/P_vs_NP/pvsnp.pdf P vs. NP] {{webarchive|url=https://web.archive.org/web/20070927212514/http://www.claymath.org/millennium/P_vs_NP/pvsnp.pdf |date=September 27, 2007 }} problem's official description by Stephen Cook on [[Millennium Prize Problems]]</ref>

In 1982, Cook received the Turing Award for his contributions to complexity theory. His citation reads:

<blockquote>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.</blockquote>

In his "Feasibly Constructive Proofs and the Propositional Calculus"<ref>{{Cite book|last=Cook|first=Stephen A.|title=Proceedings of seventh annual ACM symposium on Theory of computing - STOC '75 |chapter=Feasibly constructive proofs and the propositional calculus (Preliminary Version) |date=May 5, 1975|chapter-url=https://doi.org/10.1145/800116.803756|location=New York |publisher=Association for Computing Machinery|pages=83–97|doi=10.1145/800116.803756|isbn=978-1-4503-7419-4|s2cid=13309619 }}</ref> 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",<ref>{{Cite journal|last1=Cook|first1=Stephen A.|last2=Reckhow|first2=Robert A.|date=1979|title=The Relative Efficiency of Propositional Proof Systems|journal=The Journal of Symbolic Logic|volume=44|issue=1|pages=36–50|doi=10.2307/2273702|jstor=2273702 |s2cid=2187041 |issn=0022-4812}}</ref> 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 (complexity)|NP]] = [[coNP]]. Cook co-authored a book with his student [[Phuong The Nguyen]] in this area titled "Logical Foundations of Proof Complexity".<ref>[http://www.cup.es/us/catalogue/catalogue.asp?isbn=9780521517294 "Logical Foundations of Proof Complexity"]'s official page</ref>

His main research areas are [[computational complexity theory|complexity theory]] and [[proof complexity]], with excursions into [[programming language semantics]], [[parallel computation]], and [[artificial intelligence]]. Other areas that he has contributed to include [[bounded arithmetic]], bounded [[reverse mathematics]], [[complexity of higher type functions]], [[complexity of analysis]], and lower bounds in propositional [[proof system]]s.

===Some other contributions===
He named the complexity class [[NC (complexity)|NC]] after [[Nick Pippenger]]. The complexity class [[SC (complexity)|SC]] is named after him.<ref>{{cite web|title="Steve's class": origin of SC|url=https://cstheory.stackexchange.com/q/9298 |work=Theoretical Computer Science – Stack Exchange}}</ref> The definition of the complexity class [[AC0|AC<sup>0</sup>]] and its hierarchy [[AC (complexity)|AC]] are also introduced by him.<ref>{{cite web|title=Who introduced the complexity class AC?|url=https://cstheory.stackexchange.com/q/12649|work=Theoretical Computer Science – Stack Exchange}}</ref>

According to [[Don Knuth]] the [[KMP algorithm]] was inspired by Cook's automata for recognizing concatenated palindromes in [[linear time]].<ref>{{cite web|title=Twenty Questions for Donald Knuth|url=http://www.informit.com/articles/article.aspx?p=2213858}}</ref>

==Awards and honors==
Cook was awarded an [[NSERC]] E.W.R. Steacie Memorial Fellowship in 1977, a Killam Research Fellowship in 1982, and received the [[CRM-Fields-PIMS prize]] in 1999. He has won [[John L. Synge Award]] and [[Bernard Bolzano Medal]] of the [[Czech Academy of Sciences]] (2008),<ref>{{cite web|url=https://www.avcr.cz/en/about-us/awards/medals-of-the-cas/the-bernard-bolzano-honorary-medal-for-merit-in-the-mathematical-sciences/awarded-medals/|title=Awarded The Bernard Bolzano Honorary Medals for Merit in the Mathematical Sciences|work=Medals of the CAS|publisher=Czech Academy of Sciences|access-date=2024-04-13}}</ref> and is a fellow of the [[Royal Society of London]] and [[Royal Society of Canada]]. Cook was elected to membership in the [[United States National Academy of Sciences|National Academy of Sciences]] (United States) and the [[American Academy of Arts and Sciences]]. He is a corresponding member of the [[Göttingen Academy of Sciences and Humanities]].

Cook won the ACM [[Turing Award]] in 1982. 
[[Association for Computing Machinery]] honored him as a Fellow of [[Association for Computing Machinery|ACM]] in 2008 for his
''fundamental contributions to the theory of computational complexity''.<ref>{{Cite web|title=Stephen A Cook|url=https://awards.acm.org/award-recipients/cook_N991950|access-date=February 12, 2023|website=awards.acm.org|author1= ((Association for Computing Machinery))}}</ref>
He was selected by the [[Association for Symbolic Logic]] to give the [[Gödel Lecture]] in 1999.<ref>{{Cite web|title=Gödel Lecturers – Association for Symbolic Logic|url=https://aslonline.org/other-information/prizes-and-awards/godel-lecturers/|access-date=November 8, 2021|language=en-US}}</ref>

The [[Government of Ontario]] appointed him to the [[Order of Ontario]] in 2013, the highest honor in [[Ontario]].<ref>{{cite web|url=http://news.ontario.ca/mci/en/2013/01/25-appointees-named-to-ontarios-highest-honour.html|title=25 Appointees Named to Ontario's Highest Honour|work=Ministry of Citizenship and Immigration}}</ref> He has won the 2012 [[Gerhard Herzberg Canada Gold Medal for Science and Engineering]], the highest honor for scientists and engineers in Canada.<ref>{{cite news|first=Chung|last=Emily|url=https://www.cbc.ca/news/science/computer-scientist-wins-canada-s-top-science-prize-1.1354756|title=Computer scientist wins Canada's top science prize|publisher=cbc.ca|date=February 27, 2013|access-date=February 27, 2013}}</ref> The Herzberg Medal is awarded by [[NSERC]] for "both the sustained excellence and overall influence of research work conducted in Canada in the natural sciences or engineering".<ref>{{cite web|url=http://www.nserc-crsng.gc.ca/Prizes-Prix/Herzberg-Herzberg/Profiles-Profils/Cook-Cook_eng.asp|title=Current Winner – 2012 – Stephen Cook|date=June 28, 2016}}</ref> He was named an [[Officer of the Order of Canada]] in 2015.<ref>{{Cite web|title=SaltWire &#124; Halifax|url=https://www.saltwire.com/halifax/|access-date=February 12, 2023|website=www.saltwire.com|language=en}}</ref><ref name="OrderCanada">{{cite web | title=Order of Canada: top honours go to U of T stem cell pioneer Janet Rossant, public policy leader Bob Rae | website=University of Toronto | date=2015-07-02 | url=https://www.utoronto.ca/news/order-canada-top-honours-go-u-t-stem-cell-pioneer-janet-rossant-public-policy-leader-bob-rae | access-date=2025-03-02}}</ref>

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.<ref name="mathgenealogy">{{MathGenealogy |id=14011}}</ref>

==Personal life==
Cook lives with his wife in [[Toronto]]. They have two sons, one of whom is Olympic sailor [[Gordon Cook]].<ref>{{cite web|title=Stephen A. Cook – Home Page|url=http://www.cs.toronto.edu/~sacook/}}</ref>

==See also==
* [[List of pioneers in computer science]]

==References==
{{Reflist}}

==External links==
{{commons category}}
* [http://www.cs.toronto.edu/~sacook/ Home page of Stephen A. Cook]
* [http://msl.stream.yorku.ca/mediasite/Viewer/Viewers/Viewer320BR.aspx?mode=Default&peid=8a2b3e20-47d6-462b-9f89-eb6b9fa5b0cd&pid=06ac6222-11c0-4056-9157-2def8fb69cd8&playerType=WM64Lite 'P versus NP' and the Limits of Computation] – Public lecture given by Stephen Cook at the University of Toronto
* [http://purl.umn.edu/107226 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.
* {{MathGenealogy |name=Stephen Arthur Cook}}
* {{DBLP |name=Stephen A. Cook}}

{{FRS 1998}}
{{Turing award}}
{{Authority control}}

{{DEFAULTSORT:Cook, Stephen}}
[[Category:Living people]]
[[Category:1939 births]]
[[Category:Members of the United States National Academy of Sciences]]
[[Category:Members of the Order of Ontario]]
[[Category:Turing Award laureates]]
[[Category:Fellows of the Royal Society]]
[[Category:Fellows of the Royal Society of Canada]]
[[Category:2008 fellows of the Association for Computing Machinery]]
[[Category:Academic staff of the University of Toronto]]
[[Category:University of Michigan alumni]]
[[Category:Harvard Graduate School of Arts and Sciences alumni]]
[[Category:University of California, Berkeley College of Letters and Science faculty]]
[[Category:American emigrants to Canada]]
[[Category:Officers of the Order of Canada]]
[[Category:American theoretical computer scientists]]
[[Category:Canadian theoretical computer scientists]]