# Stephen Cook

Stephen Andrew Cook (Buffalo, 14 december 1939) is een Amerikaans theoretisch informaticus en hoogleraar aan de Universiteit van Toronto. In 1971 bewees hij dat er beslissingsproblemen bestaan waartoe alle NP-problemen in polynomiale tijd gereduceerd kunnen worden. Hiervoor ontving hij in 1982 de Turing Award.

## Levensloop

Cook werd in 1939 geboren in Buffalo in de Amerikaanse staat New York. Zijn vader was scheikundige. Zijn moeder werkte een aantal jaar als lerares Engels, maar was vooral huisvrouw.
In 1961 Cook ontving hij zijn Bachelorgraad met als hoofdvak wiskunde van de Universiteit van Michigan, en in 1962 zijn Mastergraad van de Harvard-universiteit. Na in 1966 aan diezelfde universiteit te zijn gepromoveerd kreeg hij een baan aan de Universiteit van Berkeley. Toen zijn contract in 1970 niet werd verlengd, kreeg hij een vaste baan aan de Universiteit van Toronto, waar hij sindsdien gewerkt heeft.
Cook is getrouwd en heeft twee zoons. In zijn vrije tijd houdt hij van zeilen.

## Wetenschappelijke bijdragen

Cook wordt beschouwd als een van de pioniers op het gebied van de complexiteitstheorie. In 1971 schreef hij het baanbrekende artikel The Complexity of Theorem Proving Procedures, waarin hij bewees dat er beslissingsproblemen bestaan waartoe alle NP-problemen in polynomiale tijd gereduceerd kunnen worden. In dit artikel poneerde hij ook de vraag of de klassen P en NP gelijk zijn, een vraag die later door het Clay Mathematics Institute onder de Millenniumprijsproblemen werd opgenomen. In 1982 won hij voor zijn werk in de complexiteitstheorie de Turing Award.
Naast zijn werk in de complexiteitstheorie leverde Cook ook bijdragen aan de complexiteitstheorie voor logische bewijzen, semantiek van programmeertalen en kunstmatige intelligentie.
* 1 2 Interview met Stephen Cook (Geraadpleegd 18 mei 2011)
* ↑ Biografie op de homepage van Cook. (Geraadpleegd 18 mei 2011)
* ↑ Stephen A. Cook, The Complexity of Theorem Proving Procedure, Proceedings Third Annual ACM Symposium on Theory of Computing, mei 1971
1966: Alan J. Perlis · 1967: Maurice V. Wilkes · 1968: Richard Hamming · 1969: Marvin Minsky · 1970: J.H. Wilkinson · 1971: John McCarthy · 1972: Edsger Dijkstra · 1973: Charles W. Bachman · 1974: Donald E. Knuth · 1975: Allen Newell, Herbert Simon · 1976: Michael Rabin, Dana S. Scott · 1977: John Backus · 1978: Robert W. Floyd · 1979: Kenneth E. Iverson · 1980: Tony Hoare · 1981: Edgar F. (Ted) Codd · 1982: Stephen A. Cook · 1983: Ken Thompson, Dennis M. Ritchie · 1984: Niklaus Wirth · 1985: Richard M. Karp · 1986: John Hopcroft, Robert Tarjan · 1987: John Cocke · 1988: Ivan Sutherland · 1989: William Kahan · 1990: Fernando J. Corbató · 1991: Robin Milner · 1992: Butler Lampson · 1993: Juris Hartmanis, Richard E. Stearns · 1994: Edward Feigenbaum, Raj Reddy · 1995: Manuel Blum · 1996: Amir Pnueli · 1997: Douglas Engelbart · 1998: Jim Gray · 1999: Frederick P. Brooks, Jr. · 2000: Andrew Chi-Chih Yao · 2001: Ole-Johan Dahl, Kristen Nygaard · 2002: Ron Rivest, Adi Shamir, Leonard M. Adleman · 2003: Alan Kay · 2004: Vinton G. Cerf, Robert E. Kahn · 2005: Peter Naur · 2006: Frances E. Allen · 2007: Edmund M. Clarke, E. Allen Emerson, Joseph Sifakis · 2008: Barbara Liskov · 2009: Charles Thacker · 2010: Leslie Valiant · 2011: Judea Pearl · 2012: Shafi Goldwasser, Silvio Micali · 2013: Leslie Lamport · 2014: Michael Stonebraker · 2015: Martin Hellman, Whitfield Diffie · 2016: Tim Berners-Lee · 2017: John L. Hennessy, David Patterson · 2018: Yoshua Bengio, Geoffrey Hinton, Yann LeCun · 2019: Patrick M. Hanrahan, Edwin E. Catmull · 2020: Alfred Aho, Jeffrey Ullman · 2021: Jack Dongarra · 2022: Robert Metcalfe · 2023: Avi Wigderson