Editing Stephen Cook (section)

==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>