Die 1971 veröffentlichte Arbeit mit dem Titel The Complexity of Theorem Proving Procedures schuf die formalen Grundlagen für das P-versus-NP-Problem, eine zentrale Frage der Informatik, die bis heute ungelöst ist. Verfasst von Stephen Cook, führte diese Arbeit den Begriff der NP-Vollständigkeit ein und veränderte die Art und Weise, wie Mathematiker und Informatiker die inhärente Schwierigkeit von Rechenaufgaben einordnen.
Akademischer Werdegang
Cook wurde 1939 in Buffalo geboren und absolvierte sein Hochschulstudium in den Vereinigten Staaten. Er erwarb 1961 einen Bachelor-Abschluss an der University of Michigan sowie 1962 und 1966 einen Master-Abschluss bzw. Doktortitel in Naturwissenschaften an der Harvard University. Seine Lehrtätigkeit begann er 1966 als Assistenzprofessor an der University of California, Berkeley. Nach seinem Weggang im Jahr 1970 wechselte er an die University of Toronto, wo er in den Fachbereichen Informatik und Mathematik tätig war und schließlich zum Distinguished Professor ernannt wurde.
Berechnungs-Komplexität
Cooks Forschung konzentriert sich hauptsächlich auf Komplexitätstheorie und Beweiskomplexität. Seine wegweisende Arbeit zum aussagenlogischen Erfüllbarkeitsproblem (SAT) zeigte, dass dieses Problem NP-vollständig ist – eine Entdeckung, die unabhängig davon auch von Leonid Levin gemacht wurde und heute als Satz von Cook und Levin bekannt ist. Zu seinen Beiträgen gehört auch die Definition der Komplexitätsklassen NC, SC und AC0. Neben der Komplexitätstheorie hat er sich mit parallelem Rechnen, der Semantik von Programmiersprachen und beschränkter Arithmetik befasst.
Berufliche Anerkennung
Für seine Arbeit erhielt er bedeutende internationale Auszeichnungen, darunter 1982 den ACM Turing Award für die Förderung des Verständnisses der Rechenkomplexität. Er ist Fellow der Association for Computing Machinery und Mitglied prestigeträchtiger Gremien wie der Royal Society, der National Academy of Sciences und der American Academy of Arts and Sciences. In Kanada erhielt er 2012 die Gerhard Herzberg Canada Gold Medal for Science and Engineering und wurde 2015 zum Officer des Order of Canada ernannt.
Zwanzig Fragen, acht Minuten auf der Uhr und ein Perzentil, gemessen an allen bisherigen Teilnehmern. Ohne Anmeldung.
IQ-Test starten →Kurze Fakten
- Geboren: 1939, Buffalo - Staatsbürgerschaft: Kanada und Vereinigte Staaten - Turing-Award: 1982 - Abschluss: Doktor der Wissenschaften - Akademische Heimat: University of Toronto - Bedeutende Anerkennung: Officer des Order of Canada - Forschungsgebiet: Rechenkomplexität
Häufig gestellte Fragen
### Was ist das P-vs.-NP-Problem?
Es ist die Frage, ob jedes Entscheidungsproblem mit effizient verifizierbaren Antworten auch durch einen effizienten Algorithmus gelöst werden kann.
### Was ist der Satz von Cook und Levin?
Es ist der formale Beweis dafür, dass das Erfüllbarkeitsproblem der Aussagenlogik NP-vollständig ist, unabhängig aufgestellt von Stephen Cook und Leonid Levin.
