Die Laureaten

Copyright © Klaus Tschira Stiftung / Peter Badge

Stephen A. Cook

geboren 1939 in Buffalo, New York (USA)

Turing Award (1982) „für seine Weiterentwicklung des Verständnisses der Komplexität von Berechnungen auf wesentliche und tiefschürfende Art. Sein wegweisender Aufsatz, „The Complexity of Theorem Proving Procedures“, das er 1971 auf dem ACM SIGACT Symposium on the Theory of Computing vorstellte, legte die Grundlagen der Theorie der NP-Vollständigkeit. Die anschließende Erforschung der Grenzen und Eigenschaften der Klasse NP-vollständiger Probleme wurde eine der aktivsten und wichtigsten Forschungsaktivitäten in der Informatik im letzten Jahrzehnt.“

Cook ist Sohn eines Chemikers und einer Englischlehrerin. Schon als Jugendlicher interessierte er sich für Elektronik. Er besuchte ab 1957 die University of Michigan (USA) und studierte zunächst Ingenieurwissenschaften, schwenkte dann aber auf Mathematik um (Bachelor of Science 1961). Er besuchte anschließend Harvard University (Scientiæ Magister 1962, Ph.D. 1966), wo er sich besonders für Komplexitätstheorie interessierte, die zu dem Zeitpunkt noch in den Kinderschuhen steckte. Seine Doktorarbeit „On the Minimum Computation Time of Functions“ behandelte die Komplexität von Algorithmen für die Multiplikation.

Er arbeitete anschließend als Dozent für Informatik an der University of California, Berkeley (1966-1970) und der University of Toronto, Kanada (1970-1975), wo er 1975 als Professor einen Lehrstuhl für Informatik übernahm; 1985 erhielt er den Ehrentitel University Professor.

Cook war Fellow zahlreicher Forschungseinrichtungen und ist unter anderem auch Träger des CRM-Fields Prize (1999) und der mit einem Forschungsetat von einer Million Dollar dotierten Gerhard Herzberg Canada Gold Medal for Science and Engineering (2013).

Stephen Cook nimmt gerne aktiv an Segel-Regatten teil und spielt Violine. Er ist verheiratet und hat zwei Söhne.

Das Konzept der NP-Vollständigkeit, das Cook Anfang der 1970er Jahre entwickelte, hat eine lange Vorgeschichte: 1936 veröffentlichte Alan Turin seine Idee der Turing-Maschine, eine Art Standardverfahren, um Computerprogramme zu beschreiben. Etwa 30 Jahre später brachte der Mathematiker Jack Edmonds die Idee auf, Algorithmen für Probleme wie das Sortieren von Zahlen oder das Finden einer kürzesten Rundroute durch Städte auf einer Landkarte zu vergleichen, indem man die Schritte misst, die nötig sind, die Probleme auf einer Turing-Maschine zu lösen. Klar ist, dass es länger dauert, 100 Zahlen zu sortieren als nur 10; man spricht von verschieden großen „Instanzen“ ein und desselben Problems. Edmonds fand, dass man zufrieden sein kann, wenn die Laufzeit mit der Größe der Instanzen nur mit einer begrenzten Rate ansteigt.

Stephen Cook betrachtete nun Entscheidungsprobleme, also Probleme, die mit Ja oder Nein beantwortet werden können. Beispiel: Gegeben ist eine Straßenkarte mit einer gewissen Menge von Städten. Kann man all diese Städte genau einmal besuchen, dabei keine Straße zweimal verwenden und zwar auf einer Tour, die kürzer ist als ein gewisser Wert? Klar ist: Bekommt man irgend eine Route, dann kann man – im Sinne von Edmonds – schnell überprüfen, ob sie tatsächlich eine korrekte Rundroute ist, die kürzer ist als der Wert. Doch Cook – und unabhängig von ihm auch der sowjetische Mathematiker Leonid Levin – zeigten noch mehr: Sie bewiesen, auf welche Weise viele Probleme in ihrer Komplexität äquivalent sind zu einem gewissen Referenzproblem, SAT genannt. Dazu gehört auch das Problem, auf einer Straßenkarte eine kürzeste Route tatsächlich zu finden. Heute sind tausende Probleme bekannt, für die sich angebliche Lösungen schnell testen lassen; sie zu lösen ist aber äquivalent zu einer Lösung von SAT. Dies ist die Klasse der NP-vollständigen Probleme. Für keines der Probleme in dieser Klasse ist bis heute eine schnelle Methode bekannt, Lösungen zu finden. Ist das prinzipiell unmöglich? Das ist eine der Kernfragen der modernen Mathematik, das Problem P versus NP.