Stephen Arthur CookOOnt (*14. Dezember1939 inBuffalo,New York) ist Professor derInformatik an derUniversity of Toronto inKanada. Sein Hauptbetätigungsfeld ist dieKomplexitätstheorie; Cook arbeitet neben seiner Lehrtätigkeit aber auch an der Schnittstelle vonLogik undBerechenbarkeitstheorie.
Cook wurde in dertheoretischen Informatik berühmt durch denSatz von Cook: „SAT istNP-vollständig“. 1982 bekam er für diese Entdeckung denTuring Award.
1990 hielt er einen Plenarvortrag auf demICM in Kyoto (Computational complexity of higher type functions).
Cook wuchs als Sohn eines Chemie-Professors und einer Englischlehrerin in der Nähe vonBuffalo,New York, auf. Ab 1957 studierte er Ingenieurwissenschaften an derUniversity of Michigan, wechselte nach zweieinhalb Jahren zur Mathematik und erreichte 1961 den Bachelor-Grad. Er studierte an derHarvard University weiter, wo ein Kurs seines späteren DoktorvatersHao Wang sein Interesse an Computern weckte. 1962 wurde er Master der Mathematik, 1966 mit der ThesisOn the Minimum Computation Time of Functions (darin enthalten unter anderem derToom-Cook-Algorithmus) Ph.D. Nach Studiumsende wurde er Assistenzprofessor an der mathematischen Fakultät derUniversity of California, Berkeley. Nachdem ihm dort eineStelle auf Lebenszeit verweigert wurde, wechselte er 1970 als außerordentlicher Professor an die neugegründete Fakultät für Informatik der University of Toronto, wo er zunächst auch Mathematik-Vorlesungen hielt.
1971 formalisierte er in dem PaperThe Complexity of Theorem Proving Procedures diePolynomialzeitreduktion (auch:Cook-Reduktion), und begründete mit demSatz von Cook das Konzept derNP-Vollständigkeit und im Besonderen dasP-NP-Problem. Im Jahr darauf wurde diese Arbeit von Cooks kurzzeitigem Berkeley-KollegenRichard M. Karp popularisiert und durchKarps 21 NP-vollständige Probleme erweitert.
1975 wurde er ordentlicher Professor, und 1985 erhielt er den EhrentitelUniversity Professor.
Cook ist Steacie Fellow, Killiam Research Fellow,ACM Fellow, Fellow derRoyal Society of London und derRoyal Society of Canada, und wurde in dieNational Academy of Sciences und dieAmerican Academy of Arts and Sciences gewählt. Er ist seit 1995 korrespondierendes Mitglied derAkademie der Wissenschaften zu Göttingen. 1982 erhielt er den Turing Award, 1999 erhielt er denCRM-Fields-Preis und warGödel-Lecturer. Ihm wurden dieGerhard Herzberg Canada Gold Medal for Science and Engineering für 2012 und derBBVA Foundation Frontiers of Knowledge Award für 2015 zugesprochen.
Cooks erster Doktorand warWalter Savitch (Satz von Savitch), es folgten fast 30 weitere.
| Personendaten | |
|---|---|
| NAME | Cook, Stephen A. |
| ALTERNATIVNAMEN | Cook, Stephen Arthur (vollständiger Name) |
| KURZBESCHREIBUNG | amerikanischer Informatiker, Satz von Cook |
| GEBURTSDATUM | 14. Dezember 1939 |
| GEBURTSORT | Buffalo,New York |
