Digitale Pioniere (54): Stephen A. Cook: Ein schwerer Fall

Aller Ehren wert

„SAT ist NP-vollständig“ – ein kurzer Satz, der dem Informatiker Stephen A. Cook den renommierten Turing-Preis brachte und der Informatik eine bis heute gültige Gewissheit: Es gibt Probleme, die im mathematischen Sinn wesentlich „schwieriger“ als andere sind. Für diese NP-vollständigen Probleme ist bis heute keine grundsätzlich bessere Methode bekannt, als alle Lösungen auszuprobieren.

Zur Person

Stephen Arthur Cook hat es mit dem 1971 von ihm formulierten Satz auf die Liste der Millenniumsprobleme geschafft. Sie enthält aktuell sieben besonders schwere Fälle ungelöster Probleme der Mathematik, darunter das P-NP-Problem. Es stellt die Frage, ob man NP-vollständige Probleme vielleicht doch effizient lösen kann, oder ob das grundsätzlich unmöglich ist, auch auf den schnellsten Computern.

Cook kam 1939 in Buffalo zur Welt. Nach seiner Schulzeit wollte er zuerst Ingenieur werden, wechselte aber bereits nach zwei Jahren seines Studiums an der Universität von Michigan zur dortigen Mathematik-Fakultät, wo er 1961 seinen Bachelor ablegte. Anschließend ging es zum Master-Studium nach Harvard. Der Abschluss folgte schon im Jahr darauf. Vier Jahre später, 1966, promovierte Cook. Als nächste Station folgte eine Stelle als Assistenzprofessor an der Universität von Kalifornien, die er nach kurzer Zeit wieder verließ. Er ging 1970 an die Universität Toronto, an der er als Professor bis zu seinem Ruhestand forschte und lehrte.

Unabhängig von Stephen A. Cook hat der später in die USA emigrierte russische Informatiker Leonid Levin 1973 einen inhaltlich gleichen Satz formuliert. Deshalb wird der heute oft auch als „Satz von Cook und Levin“ bezeichnet. Bereits rund 20 Jahre zuvor beschrieb Kurt Gödel, Mathematiker und einer der bedeutendsten Logiker der 20. Jahrhunderts, das Problem in einem Briefwechsel mit John von Neumann, dem Vater der Architektur fast aller modernen Computer.

Gut zu wissen
Dass es Probleme gibt, die mit aktuell verfügbarer Rechentechnik und Methodik nicht in vertretbarer Zeit gelöst werden können, machen sich heutzutage moderne Verschlüsselungstechniken zunutze. Sie gelten als derzeit unknackbar und damit als sicher.

Vor 75 Jahren stellte Konrad Zuse den ersten funktionsfähigen Computer Z3 in Berlin vor. Aus diesem Anlass blicken das Zuse-Institut Berlin und der Tagesspiegel am 11. Mai auf einer internationalen Konferenz in die digitale Zukunft: „The Digital Future – 75 Years Zuse Z3 and the Digital Revolution.“  75 Folgen über die wichtigsten Wegbereiter des digitalen Zeitalters zeigen, was bisher geschah. Mehr zur Veranstaltung: www.science-match.info

Jan Rähm