Fact-checked by Grok 2 weeks ago

Stephen Cook

Stephen A. Cook (born , 1939) is an American-Canadian and University Professor Emeritus at the , best known for pioneering the theory of in , which has profoundly influenced modern and . His seminal 1971 paper, "The Complexity of Theorem-Proving Procedures," established that the is NP-complete, laying the groundwork for understanding the hardest problems in NP and inspiring Richard Karp's subsequent identification of 21 additional NP-complete problems. Cook's work has earned him the prestigious ACM Turing Award in 1982, often called the " of computing," for advancing the theory of and demonstrating the central role of logic in this field. Born in Buffalo, New York, Cook developed an early interest in electronics during his teenage years after moving to Clarence, New York, at age 10. He earned his B.Sc. in mathematics from the University of Michigan in 1961, followed by an S.M. in 1962 and a Ph.D. in 1966, both from Harvard University, where his doctoral research exposed him to early ideas in computational complexity under the supervision of Hao Wang. After completing his Ph.D., Cook joined the University of California, Berkeley, as an assistant professor from 1966 to 1970, before moving to the University of Toronto as an associate professor in 1970, where he was promoted to full professor in 1975 and later appointed University Professor in 1985. He has supervised over 30 Ph.D. students and continues to reside in Toronto with his wife and two sons, while pursuing interests such as sailing. Beyond NP-completeness, Cook has made significant contributions to propositional proof complexity, founding the field with his work on the lengths of proofs in propositional calculus, and co-developing the Toom-Cook algorithm for fast multiplication of large integers. His research interests also encompass programming language semantics, parallel computation, and the interplay between logic and complexity theory, resulting in over 50 published papers that have shaped foundational questions in theoretical computer science. Cook's accolades include the 2012 NSERC Gerhard Herzberg Canada Gold Medal, the 1999 CRM-Fields Prize, the 1997 Canada Council Killam Prize, and the 2016 Canadian Association of Computer Science Lifetime Achievement Award, along with fellowships in the Royal Society of London, the Royal Society of Canada, the American Academy of Arts and Sciences, and the ACM, as well as membership in the U.S. National Academy of Sciences.

Biography

Early Life and Education

Stephen Arthur Cook was born on December 14, 1939, in Buffalo, New York, to American parents. His father worked as a chemist for a subsidiary of Union Carbide and served as an adjunct professor at the State University of New York at Buffalo, while his mother was a homemaker who occasionally taught English at Erie Community College. The family relocated to Clarence, New York, when Cook was ten years old. During his childhood, he developed an early interest in science, particularly electronics, influenced by his father's profession. As a teenager in high school, he worked with local inventor Wilson Greatbatch—known for developing the implantable cardiac pacemaker—on projects involving transistor-based circuitry, which further nurtured his scientific curiosity. Cook also showed aptitude in mathematics, attending Clarence Central School where he was recognized in science and math activities. Cook entered the in 1957 and received a degree in in 1961. He then pursued graduate studies at , earning a degree in in 1962. In 1966, he completed his in at Harvard, with a dissertation titled On the Minimum Computation Time of Functions under the supervision of Hao Wang.

Academic Career

Cook began his academic career as an Assistant Professor in the Department at the , from 1966 to 1970. During this period, he conducted research at the intersection of and emerging topics, though his tenure review focused primarily on mathematical contributions. In 1970, the Berkeley Department denied him reappointment, prompting his relocation to . That same year, Cook joined the as an in the Department of , with a joint appointment in the Department of Mathematics. He was promoted to full Professor in 1975 and further elevated to University Professor—the institution's highest academic distinction—in 1985. Cook continued in this role until his appointment as University Professor Emeritus, maintaining an active affiliation with the department. Throughout his tenure at Toronto, Cook played a key role in developing the computer science program through mentorship and teaching, supervising 33 Ph.D. students and earning departmental teaching awards in 1989 and 1995. As of 2025, he remains engaged with the academic community, including recognition during the University of Toronto Department of Computer Science's 60th anniversary celebration in 2024, where his foundational contributions were honored.

Research Contributions

Complexity Theory

Stephen Cook's foundational contributions to computational complexity theory emerged from his earlier work in computability during the late 1960s. His 1966 PhD thesis at , titled "On the Minimum Computation Time of Functions," supervised by Hao Wang, explored the intrinsic of operations like , building on concepts from Alan Turing's 1936 model to analyze minimum time requirements for function computation on Turing machines. One key outcome was an improvement to Andrei Toom's algorithm for large integers, now known as the Toom-Cook algorithm, which achieves better asymptotic performance than schoolbook for sufficiently large operands. This work marked Cook's transition from undecidability and —fields dominant in the 1930s through —to the emerging study of resource-bounded computation, influenced by the need to distinguish "tractable" problems in practical algorithm design. Prior to 1971, computational complexity theory was in its infancy, focusing on hierarchies of time and rather than relative hardness within bounded resources. Key developments included Juris Hartmanis and Richard Stearns' 1965 formalization of time and space measures for multitape Turing machines, which established basic hierarchies showing that more time allows solving harder problems, and Alan Cobham's 1964 notion of polynomial-time computability as a model-independent standard for efficiency. ' 1965 work on "good algorithms" informally introduced nondeterministic polynomial-time computation in the context of problems like , highlighting the gap between deterministic and nondeterministic efficiency. These advances set the stage for Cook's innovations by shifting attention from infinite to finite-resource limitations, but lacked a framework for identifying inherently hard problems within polynomial bounds. Cook's seminal 1971 paper, "The Complexity of Theorem-Proving Procedures," presented at the Third Annual ACM Symposium on Theory of Computing (STOC), introduced the concept of , revolutionizing the field. He defined the as the set of decision problems solvable by a in time, where a nondeterministic machine can "guess" a solution and verify it efficiently. To establish a benchmark for hardness, Cook proved that the (SAT)—determining whether a given Boolean formula in has a satisfying assignment—is -complete. This result, known as the Cook-Levin theorem, demonstrates that any problem in can be reduced to SAT in time via a P-reducibility (a polynomial-time computable mapping preserving membership). The core of the Cook-Levin theorem lies in the polynomial-time reduction from an arbitrary nondeterministic Turing machine computation to a SAT formula. For a nondeterministic Turing machine M that accepts an input w of length n in time q(n), Cook constructs a Boolean formula A(w, M) in conjunctive normal form with variables representing the machine's configuration at each time step i (for i = 1 to q(n)). These variables include symbols for tape contents (e.g., P_{i,j,s} indicating symbol s at tape position j in step i), head positions, and states (e.g., Q_{i,t} for state t at step i). The formula A(w, M) encodes the initial configuration (with w on the tape), the transition rules of M (ensuring each step follows the machine's nondeterministic choices), and the accepting configuration (reaching an accept state). The clauses enforce consistency across steps, such as no overlapping symbols on the tape or valid state-head movements, using auxiliary variables to simulate logical implications without exponential blowup. This construction ensures A(w, M) is satisfiable if and only if M accepts w, and the formula has size polynomial in n, completable in polynomial time. Cook highlighted theorem proving as a key example, showing that automated theorem proving in first-order predicate calculus (with bounded proof length) is NP-complete, as it reduces to checking satisfiability of formula instances derived from resolution steps. The paper also posed the , questioning whether every problem in is solvable by a deterministic in polynomial time (i.e., whether = ), framing it as a central open challenge in with profound implications for design and optimization. Post-1971, Cook's work catalyzed explosive growth in the field; it inspired Richard Karp's 1972 identification of 21 problems across and logic, establishing NP-completeness as the standard for intractability and shifting research toward approximations and parameterized .

Proof Complexity

Stephen Cook's foundational contributions to proof complexity began with his 1974 collaboration with Robert Reckhow, where they introduced the theory of feasible proofs and formalized the notion of p-bounded propositional proof systems. In their seminal paper, they defined an abstract proof system as one where proofs can be verified in polynomial time and demonstrated that if such a system exists for all propositional tautologies, then = . This work established the framework for analyzing the computational resources required for proofs, shifting focus from mere existence to the lengths of proofs in formal systems. Their approach emphasized polynomially verifiable proofs, laying the groundwork for subsequent studies in the field. Building on this, Cook and Reckhow's 1979 paper examined the relative efficiency of various propositional proof systems, particularly focusing on Frege systems—which use a of axiom schemas and —and their extensions. They proved that all Frege systems are p-equivalent, meaning proofs in one can be efficiently simulated by another, regardless of the choice of connectives. Furthermore, they showed that extended Frege systems, which allow iterative abbreviations for subformulas, are also p-equivalent among themselves and can simulate standard Frege systems with only polynomial overhead. This equivalence result highlighted the structural similarities across proof systems and influenced the classification of proof complexities. Cook made significant advances in establishing lower bounds for specific proof systems, notably in his 1990 work with Toniann Pitassi, which provided a feasibly constructive exponential lower bound for proofs of the . This result demonstrated that , a widely used system for SAT solving, requires superpolynomial proof lengths for certain tautologies, providing concrete evidence of its limitations. Their method relied on combinatorial arguments that yield explicit hard instances, advancing techniques for deriving lower bounds in proof complexity. Cook also explored deep connections between proof complexity and , particularly through the lens of bounded arithmetic systems like PV (Peano Arithmetic with induction restricted to polynomial-time verifiable formulas). In his 2010 book with Phuong Nguyen, he detailed how conservation results in these systems imply separations in proof lengths, linking propositional proofs to the computational power of circuits via feasible reasoning. For instance, lower bounds in extended Frege systems relate to limitations in constant-depth circuits with counting gates, underscoring the interplay between logical and circuit-based models of computation. These insights have implications for unresolved questions like P vs. NP, as superpolynomial proof lengths in strong systems suggest barriers to efficient theorem proving. Key papers by Cook on proof lengths include the 1974 STOC paper with Reckhow on feasible proofs and the 1979 Journal of Symbolic Logic paper on system efficiencies, both of which remain central to the field. His ongoing research interests in proof complexity persist as of 2025, evidenced by the 2023 ACM Books collection "Logic, Automata, and Computational Complexity: The Works of Stephen A. Cook," which reprints and contextualizes his influential papers on propositional proofs and their ties to complexity theory.

Other Contributions

Cook made significant contributions to the classification of problems solvable efficiently in models. In his 1979 paper, he introduced the NC, named "Nick's Class" in honor of Nick Pippenger's work on , encompassing problems that can be solved by uniform families of circuits of polylogarithmic depth and size, or equivalently by Turing machines using processors and polylogarithmic time. In the same work, he defined a related class for problems solvable in time and logarithmic squared space, later termed SC or "Steve's Class" in recognition of his foundational role. Building on these ideas, Cook's 1985 paper systematized complexity by introducing the AC hierarchy, including AC^0 for constant-depth alternating circuits with size, which captures problems amenable to very shallow computations and has been pivotal in studying limitations of constant-depth circuits. Cook's early research on automata influenced efficient string processing algorithms. His development of linear-time simulations for deterministic two-way pushdown automata enabled the recognition of complex languages, such as those involving concatenated , in linear time using multi-tape Turing machines. This work inspired the Knuth-Morris-Pratt (KMP) for string matching, as noted that the automaton-based approach to handling pattern overlaps in palindrome recognition directly informed the failure function in KMP, allowing linear-time searches without . During the 1960s and 1970s, Cook advanced and s through analyses of time and space bounds for recognizing context-free languages. His 1971 results showed that deterministic context-free languages could be recognized in linear time by simulating two-way pushdown automata on random-access machines, bridging automata models with efficiency. These contributions clarified the computational power of pushdown automata relative to time-bounded s, influencing the understanding of formal language hierarchies. Cook explored time-space tradeoffs in several works, establishing fundamental limits on computational resources. In 1973, he proved that recognizing certain languages requires either superlinear time or superlogarithmic space, using solvable path systems to demonstrate inherent tradeoffs in Turing machine models. Collaborating with Allan Borodin in 1982, he derived tight time-space bounds for sorting on general sequential models, showing that sorting n elements necessitates at least n log n time or n^{1+ε} space for any ε > 0, with implications for practical algorithm design. Cook also contributed to programming language semantics, particularly in defining for programming languages. In his 1978 paper "On the Existence of Cook Semantics," he explored conditions under which a programming language admits a certain type of , linking it to complexity-theoretic notions and influencing for program . In logic and , Cook extended complexity notions to formal proof systems, providing foundations for analyzing computational aspects of deduction. His 1975 paper introduced feasibly constructive proofs in propositional logic, linking polynomial-time verifiable proofs to bounded arithmetic and influencing automated techniques for ensuring program correctness.

Awards and Honors

Major Computing Awards

In 1977, Stephen Cook received the NSERC E.W.R. Steacie Memorial Fellowship, awarded by the Natural Sciences and Engineering Research Council of Canada to recognize early-career researchers for their potential to make significant contributions to the natural sciences and engineering, particularly in computational complexity theory. Cook was awarded the ACM Turing Award in 1982, the Association for Computing Machinery's highest honor for contributions to computer science, presented solely to him at the ACM Annual Conference in Dallas on October 25, 1982. The citation praised his work for "advancement of our understanding of the complexity of computation in a significant and profound way," specifically highlighting his 1971 paper "The Complexity of Theorem-Proving Procedures," which introduced the concept of NP-completeness and its implications for computational complexity. In 1999, Cook was honored with the CRM-Fields-PIMS Prize, a joint award from the Centre de Recherches Mathématiques, the Fields Institute, and the Pacific Institute for the , recognizing exceptional achievements by researchers under 60 in the , with particular emphasis on his foundational role in , including . The Royal Society of Canada presented Cook with the John L. Synge Award in 2006 for his outstanding research contributions to the , notably in and proof complexity. In 2008, Cook received the Medal for Merit in the Mathematical Sciences from the , recognizing his seminal contributions to and . Cook was named an in 2008 by the Association for Computing Machinery, acknowledging his fundamental contributions to the theory of . In 2016, Cook received the BBVA Foundation Frontiers of Knowledge Award in the Information and Communication Technologies category for determining that some problems do not lend themselves to efficiently computable solutions, highlighting his role in identifying computational limits. Also in 2016, he was awarded the Canadian Association of Lifetime Achievement Award for his enduring impact on the field.

National and Academic Honors

Stephen Cook, a dual American-Canadian citizen and longtime professor at the University of Toronto, has received numerous national and academic honors recognizing his contributions to science. In 1997, he was awarded the Canada Council Izaak Walton Killam Memorial Prize for Natural Sciences, one of Canada's most prestigious research awards, honoring outstanding contributions to scholarly and scientific inquiry. In 2012, Cook received the NSERC Gerhard Herzberg Canada Gold Medal for Science and Engineering, the nation's highest honor for sustained excellence and influence in research, accompanied by $1 million in funding over five years to support further work. Cook was appointed to the in 2013, the province's highest civilian honor, for his pioneering role in and broader impact on science. Two years later, in 2015, he was named an Officer of the , the country's most esteemed award for lifetime achievement, citing his seminal advancements in . Academically, Cook was elected a of Canada in recognition of his scholarly excellence. He was elected a (London) in 1998. He was also elected to the American Academy of Arts and Sciences in 1986 and the in 1985, affirming his standing among the world's leading intellectuals. Additionally, he holds honorary degrees, including a Doctor of Mathematics from the in 1999.

Personal Life and Legacy

Family and Residence

Stephen Cook is married to Linda Cook, with whom he shares life in , , . The couple has two sons. Cook holds dual and Canadian citizenship, reflecting his long-term integration into Canadian society after moving there in 1970. As of 2025, Cook resides in , where he serves as University Professor Emeritus at the . In retirement, he maintains an active lifestyle centered around , as a long-time member of the Royal Canadian Yacht Club.

Influence on the Field

Cook's mentorship has profoundly shaped the field of , with him supervising 36 PhD students at the , many focusing on topics such as propositional proof systems and bounded arithmetic. Notable among them is Robert A. Reckhow, who completed his PhD in 1976 and co-authored the seminal 1979 paper with Cook establishing the Cook-Reckhow definition of propositional proof systems, which formalized efficiency measures for proofs and remains foundational in proof . Other students, including François Pitt (2000) and Robert Robere (2018), have advanced areas like parallel computation and proof complexity under his guidance. His 1971 paper, "The Complexity of Theorem-Proving Procedures," which introduced the concept of and the P vs. NP question, has garnered over 5,000 citations, underscoring its enduring impact on . This work directly influenced the formulation of the Clay Mathematics Institute's , for which Cook authored the official description of the P vs. NP problem in 2000, highlighting its status as one of the most profound open questions in and computation. Cook's foundational contributions to have extended to modern subfields, including quantum complexity, where the P vs. NP framework informs questions about quantum versus classical computational power, such as the quantum analog of in problems like quantum . In verification, his establishment of the (SAT) as NP-complete has driven the development of SAT solvers, which are now essential tools for verifying , software, and systems, enabling automated checks for correctness in complex models. In 2024, the University of Toronto's Department of Computer Science celebrated its 60th anniversary, prominently featuring Cook's groundbreaking "Cook's Theorem" and his Turing Award-winning contributions to as pivotal to the department's legacy in advancing computational limits. Cook has issued notable challenges to stimulate research, such as in the late 2000s when he and Pierre McKenzie devised the tree evaluation problem to probe the minimal memory requirements for algorithms, conjecturing tight bounds on space usage that continue to inspire work on memory-efficient computation. His broader legacy includes popularizing through influential lectures, such as his 1982 ACM lecture "An Overview of ," which surveyed key concepts and barriers in , and co-authored like Logical Foundations of Proof Complexity (2010), which elucidates between bounded arithmetic and proof systems for audiences. These efforts, alongside collected works in Logic, Automata, and : The Works of Stephen A. Cook (2023), have made abstract notions accessible and central to ongoing theoretical advancements.

References

  1. [1]
    Stephen A Cook - A.M. Turing Award Laureate
    Cook entered the University of Michigan in 1957, majoring in science engineering. He was introduced to computer programming in a freshman course taught by ...
  2. [2]
    Stephen A. Cook -- Bio - Computer Science
    Stephen Cook is University Professor Emeritus of Computer Science at the University of Toronto. He is the 1982 Turing Award Winner and the 2012 winner of the ...Missing: biography | Show results with:biography
  3. [3]
    The complexity of theorem-proving procedures - ACM Digital Library
    S. A. Cook: Characterizations of Pushdown Machines in terms of Time-Bounded Computers. ... The Complexity of Theorem-Proving Procedures. Logic, Automata, and ...
  4. [4]
    Stephen Cook - Fields Institute for Research in Mathematical Sciences
    Stephen Cook was born in Buffalo, New York. He received his B.Sc. degree from the University of Michigan in 1961 and his SM and PhD degrees from Harvard ...Missing: biography | Show results with:biography
  5. [5]
    [PDF] Stephen Cook 1982 ACM Turing Award recipient Interviewed by ...
    Feb 25, 2016 · Professor. Cook received the ACM Turing Award in 1982 in recognition for his contributions to the theory of computational complexity, and in ...Missing: biography | Show results with:biography
  6. [6]
    Clarence Central School - Saga Yearbook (Clarence, NY)
    ... high school career. Our Soph Hop found everyone Swinging on a Star. Gene ... STEPHEN COOK Nhat I can t see I never ul l l be l leve Mayor Scxence Math ...
  7. [7]
    Stephen Cook - The Mathematics Genealogy Project
    Stephen Arthur Cook, MathSciNet, Ph.D. Harvard University 1966 UnitedStates, Dissertation: On the Minimum Computation Time of Functions.Missing: thesis | Show results with:thesis
  8. [8]
    An Interview with Stephen A. Cook - Communications of the ACM
    Jan 1, 2012 · A condensed version of an interview with AM Turing Award recipient and ACM Fellow Stephen A. Cook, considered one of the forefathers of computational ...Missing: biography | Show results with:biography
  9. [9]
    NSERC - Award of Excellence - Past Winner - Stephen Cook
    Jul 23, 2020 · Stephen Arthur Cook was born in Buffalo, New York in 1939. He received his B.Sc. degree from the University of Michigan in 1961, and his ...Missing: family background
  10. [10]
    Stephen Cook: Celebrating a half century of computational ...
    Jun 11, 2019 · Cook spent the next four years at the University of California, Berkeley, until in 1970 he was enticed into becoming an associate professor at U ...Missing: biography | Show results with:biography
  11. [11]
    Stephen A. Cook -- Home page - Computer Science
    Stephen A. Cook. University Professor Emeritus Department of Computer Science University of Toronto Toronto, Canada M5S 3G4. Tel: (416) 978-5183Missing: positions | Show results with:positions
  12. [12]
    Stephen A. Cook -- Bio - Computer Science
    Stephen Cook is University Professor Emeritus of Computer Science at the University of Toronto. He is the 1982 Turing Award Winner.
  13. [13]
    Celebrating 60 years of computer science at U of T
    Sep 12, 2024 · ... University Professor Emeritus Stephen Cook was honoured with the Turing Award in 1982 for his work on computational theory.<|separator|>
  14. [14]
    [PDF] A Short History of Computational Complexity - Lance Fortnow
    Nov 14, 2002 · The work of Cook and Karp in the early 70's showed a large number of combinatorial and logical problems were NP-complete, i.e., as hard as any ...
  15. [15]
    On the lengths of proofs in the propositional calculus (Preliminary ...
    The complexity of theorem-proving procedures, by S.A. Cook. Proceedings of Third Annual ACM Symposium on Theory of Computing, May, 1971. Digital Library.
  16. [16]
    The relative efficiency of propositional proof systems
    Mar 12, 2014 · In §4 we introduce extended Frege systems, which allow introduction of abbreviations for formulas. Since these abbreviations can be iterated, ...
  17. [17]
    A feasibly constructive lower bound for resolution proofs
    A feasibly constructive lower bound for resolution proofs☆. Author links open overlay panel. Stephen Cook , Toniann Pitassi. Show more. Add to Mendeley. Share.
  18. [18]
    The Works of Stephen A. Cook | ACM Books
    May 23, 2023 · Professor Stephen A. Cook is a pioneer of the theory of computational complexity. His work on NP-completeness and the P vs. NP problem remains a central focus ...
  19. [19]
    A taxonomy of problems with fast parallel algorithms - ScienceDirect
    The class NC consists of problems solvable very fast (in time polynomial in log n) in parallel with a feasible (polynomial) number of processors.
  20. [20]
    Fast Pattern Matching in Strings | SIAM Journal on Computing
    Hybrid pattern-matching algorithm based on BM-KMP algorithm. 2010 3rd ... 5. Stephen A. Cook, Linear time simulation of deterministic two-way pushdown ...
  21. [21]
    Twenty Questions for Donald Knuth - InformIT
    May 20, 2014 · ... Steve Cook's automata was able to recognize concatenated palindromes in linear time. Such investigations are fun. A few months ago, however ...
  22. [22]
    Linear Time Simulation of Deterministic Two-Way Pushdown Automata
    Linear Time Simulation of Deterministic Two-Way Pushdown Automata · S. Cook · Published in IFIP Congress 1971 · Computer Science, Mathematics.Missing: KMP | Show results with:KMP
  23. [23]
    An observation on time-storage trade off - ACM Digital Library
    An observation on time-storage trade off. Author: Stephen A. Cook ... S. A. Cook, Characterizations of Pushdown Machines in Terms of Time-Bounded Computers.
  24. [24]
    [PDF] An Overview of Computational Complexity, 1982
    The 1982 Taring Award was presented to Stephen Arthur Cook, Professor of Computer Science at the University of Toronto, at the ACM Annual. Conference in ...
  25. [25]
    1999 CRM-Fields Prize awarded to Stephen A. Cook
    The 1999 CRM-Fields Prize is awarded to Stephen A. Cook from the University of Toronto. Dr. Cook's principal research area is computational complexity.
  26. [26]
    Mathematics People
    STEPHEN A. COOK of the University of Toronto has been awarded the John L. Synge Award of the Royal Society of. Canada (RSC). He ...
  27. [27]
    Stephen A Cook - ACM Awards
    ACM Fellows. Canada - 2008. citation. For fundamental contributions to the theory of computational complexity. ACM A. M. Turing Award.
  28. [28]
    NSERC - Gerhard Herzberg Canada Gold Medal for Science and ...
    Sep 10, 2025 · Past Winner 2012 NSERC Gerhard Herzberg Canada Gold Medal for Science and Engineering. Stephen Cook. Computer Science and Mathematics.
  29. [29]
    25 Appointees Named to Ontario's Highest Honour
    Jan 31, 2013 · Stephen Cook is one of the world's most recognized and influential computer scientists. ... Created in 1986, the Order of Ontario, the province's ...
  30. [30]
    Dr. Stephen Cook | The Governor General of Canada
    Stephen Cook has made legendary contributions at the intersection of mathematics and computer science. A professor at the University of Toronto since 1970 ...Missing: founding | Show results with:founding
  31. [31]
    Stephen A. Cook
    - **Election Year**: 1986
  32. [32]
    Honorary Degrees Granted - Alphabetical Order | Secretariat
    Cook, Stephen, Doctor of Mathematics. 2016, Cooper, James, Doctor of ... The University of Waterloo acknowledges that much of our work takes place on ...
  33. [33]
    [PDF] The BBVA Foundation Frontiers of Knowledge Award goes to ...
    Jan 12, 2016 · Stephen Arthur Cook (Buffalo, New York, United States, 1939) holds dual American and Canadian nationality.Missing: citizenship | Show results with:citizenship
  34. [34]
    Stephen A. Cook: Computer Science H-index & Awards
    Stephen A. Cook mainly investigates Discrete mathematics, Combinatorics, Complexity class, Function and Time complexity.Missing: positions Berkeley
  35. [35]
    [PDF] The P versus NP problem - Clay Mathematics Institute
    Statement of the Problem. The P versus NP problem is to determine whether every language accepted by some nondeterministic algorithm in polynomial time is ...
  36. [36]
    Complexity Theory's 50-Year Journey to the Limits of Knowledge
    Aug 17, 2023 · ... before the beginning of modern computer science. In 1921 ... Stephen Cook formulated the P versus NP problem in the early 1970s ...
  37. [37]
    Understanding the SAT Problem in Computer ... - AI-FutureSchool
    Stephen Cook, 1939–, Stephen Cook is renowned for formulating the SAT problem in his 1971 paper, where he introduced the concept of NP-completeness. His work ...
  38. [38]
    Celebrating 60 years of computer science at U of T
    Sep 11, 2024 · Stephen Cook. University Professor Emeritus Stephen Cook was honoured with the Turing Award in 1982 for his work on computational theory.
  39. [39]
    Catalytic Computing Taps the Full Power of a Full Hard Drive
    Feb 18, 2025 · Stephen Cook devised a computational task, called the tree evaluation problem, that seemed impossible for any algorithm with limited memory.
  40. [40]
    https://www.claymath.org/wp-content/uploads/2022/06/pvsnp.pdf