Der Vater des (vermutlich) Unlösbaren: Stephen A. Cook

BLOG: Heidelberg Laureate Forum

Laureates of mathematics and computer science meet the next generation
Heidelberg Laureate Forum
Stephen A. Cook
Stephen A. Cook
© Klaus Tschira Stiftung / Peter Badge

“Stephen Arthur Cook” ist einer jener Namen, welche (hoffentlich) jeder Informatikabsolvent, und zumindest jeder zweite frisch gebackene Mathematiker, im Rahmen des jeweiligen Studiums kennen und bewundern gelernt hat. War es doch Cook, der 1971 in seinem Artikel “The Complexity of Theorem Proving Procedures” (TB: deutsch “Die Komplexität von Methoden des Theorembeweisens“) im Alleingang die Grundlagen eines wichtigen Teilgebiets der Komplexitätstheorie, nämlich der Theorie der NP-Vollständigkeit, gelegt hat – und gleichzeitig auch die heute fast schon in der Popkultur angekommene Gretchenfrage der theoretischen Informatik “P vs. NP” formulierte. Im Rahmen des Heidelberg Laureate Forums 2013 hatte ich Gelegenheit, mich einige Minuten mit dem Turing Award-Preisträger des Jahres 1982 über seine Arbeit und seinen Lebensweg zu unterhalten.

Stephen A. Cook wurde 1939 in Buffalo, NY in den USA geboren, erwarb 1961 einen Bachelorabschluss in Mathematik an der University of Michigan, und promovierte 1966 im Fachbereich Mathematik der Harvard University (USA) mit einer frühen komplexitätstheoretischen Arbeit zu spezifischen Eigenschaften der Multiplikation. Danach führte ihn sein Weg an die University of California in Berkeley (USA), bevor er 1970 seine Position als Professor der Informatik an der University of Toronto in Kanada aufnahm, wo er (parallel zu kontinuierlichen, wichtigen Beiträgen zur Komplexitätstheorie und benachbarten Gebieten) bis dato mehr als 30 Doktoranden und zahlreiche Masterarbeiten betreute und weiterhin betreut – wenn er nicht gerade aktiv seiner Leidenschaft Segeln nachgeht.

Aber Moment, was ist eigentlich Komplexitätstheorie? Dabei handelt es sich um ein Gebiet im Grenzbereich zwischen Mathematik, Logik, und theoretischer Informatik, das grundsätzlich die Frage nach dem Ressourcenverbrauch von Algorithmen (also etwa der benötigten Anzahl an Rechenschritten, oder dem Bedarf an Speichereinheiten, bei der Ausführung eines gewissen Algorithmus) stellt. Entscheidend hierbei ist, dass gefundene Resultate zumeist intrinsische Eigenschaften eines Algorithmus beschreiben, also eine Charakterisierung des Platz- oder Zeitverbrauches unabhängig vom konkreten Laptop, PC oder Großrechner, auf welchem ein Programm läuft, darstellen.

Cooks 1971er Beitrag zu dieser Forschungsrichtung erwies sich dabei als richtungsbestimmend für die weitere Entwicklung des ganzen Gebiets. Es zeigt sich, dass sich Algorithmen anhand ihres jeweiligen Ressourcenverbrauchs in Klassen einteilen lassen, welche wiederum eine Hierarchie ergeben: Die Klasse der einfach (d.h. ressourcenschonend) lösbaren Probleme ist dabei eine Unterklasse der schon etwas fordernderen Probleme, welche wiederum in der nächsten Oberklasse enthalten sind. Und auch innerhalb der einzelnen Klassen ergeben sich interessante Zusammenhänge: So sind Algorithmen innerhalb einer Klasse gemeinhin mit wenig Aufwand ineinander überführbar (gegeben den Input X und den Output Y von Algorithmus A ist es also möglich, mit vergleichsweise geringem Ressourcenverbrauch den Output von Algorithmus B zu Input X zu berechnen, vorausgesetzt dass A und B in derselben Komplexitätsklasse liegen). Und Stephen A. Cook war nun eben derjenige, der erstmalig eine Charakterisierung der NP-Vollständigkeit eines Problems gab – also formal definierte, was es heißt, dass ein Problem wirklich in NP (eine der höheren Hierarchieklassen) liegt, und wahrscheinlich keine effiziente Lösung zulässt.

Wieso dies weitreichende Folgen hat? Nun, beispielsweise bilden eben diese “wahrscheinlich nicht effizient lösbaren” Probleme die Grundlage moderner Verschlüsselungstechniken, vom Onlinebanking bis hin zur codierten Email: In fast allen kryptographischen Methoden ist heutzutage ein NP-vollständiges Problem versteckt, welches (so hofft man zumindest) nicht oder nur mit Glück durch naive, auf purer Rechenleistung beruhende Versuche zu lösen ist, sondern (gemeinhin Außenstehenden nicht zugängliches) Zusatzwissen voraussetzt. Und hier kommt nun auch “P vs. NP” ins Spiel: P bezeichnet in der Komplexitätstheorie eben eine Klasse an Problemen, welche gemeinhin relativ leicht lösbar sind, NP steht für die bereits angesprochenen schwierigen Probleme – und “P vs. NP” stellt die Frage, ob beide Klassen wirklich grundsätzlich unterschiedlich sind, oder ob nicht doch NP und P gleich sind, und es uns nur noch nicht gelungen ist, herauszufinden, mit welcher Methode Probleme in NP vergleichsweise einfach zu lösen wären. Sicherer digitaler Geldtransfer adé.

Aber Komplexitätstheorie beschränkt sich heute nicht mehr nur auf Berechnungen im Informatikkontext. Der Anspruch ist hierbei viel globaler: Jede Art von Berechnung ist potentiell mit Methoden des Gebiets analysierbar – und dabei spreche ich zum Beispiel auch von den Berechnungen, welche das Gehirn im Rahmen von menschlichen Problemlöseprozessen ausführen muss, oder Fragen nach evolutionärem Zusammenhängen in der Systembiologie (zum Beispiel indem ein Biosystem als großer, natürlicher Rechner aufgefasst wird, und betrachtet wird, ob gewisse Adaptionsprozesse gegeben die vorhandenen Ressourcen innerhalb eines begrenzten Zeitraums hätten ablaufen können). Ohne Stephen A. Cooks zahlreiche Beiträge wäre vieles hiervon so nicht denkbar.

PS: Eine korrekte Antwort auf die Frage, ob P gleich NP ist (oder eben nicht), ist im Übrigen nicht “nur” mit akademischer Unsterblichkeit und Nachruhm verbunden – sondern ist inzwischen, dem Clay Mathematics Institute sei Dank, auch mit einem Preisgeld von einer Million US-Dollar dotiert.

Tarek R. Besold

arbeitet als PostDoc zu verschiedenen Themen aus dem Dunstkreis "Künstliche Intelligenz und Künstliche Kreativität" am Institut für Kognitionswissenschaft der Universität Osnabrück. Vor seiner Promotion in Kognitionswissenschaft hatte er Mathematik mit Nebenfach Informatik studiert, und ein einjähriges Intermezzo als "Logic Year"-Gaststudent an der Universität Amsterdam verbracht. Neben seiner eigentlichen Forschungsarbeit engagiert er sich als Wissenschaftskommunikator (zweiter Gewinner des 2013er Falling Walls Lab "Young Innovator of the Year"-Preises), Mitveranstalter von Wissenschaftsevents und gelegentlicher Autor des Analogia-SciLogs-Blog tätig.

2 comments

  1. Guter Artikel, der in Kürze relativ viel erklärt. Der Titel erscheint mir aber etwas unglücklich. NP-vollständig bedeutet nicht Unlösbar, sondern lediglich “nur mit hohem Aufwand lösbar” und unlösbar ab einer bestimmten Problemgrösse. Jeder Mensch löst im Alltag solch “unlösbare” Probleme zuhauf. 5 Städte in optimaler Reihenfolge besuchen: Kein Problem. 1000 Städte in optimaler Reihenfolge besuchen: Welcher Mensch hat in der Praxis ein solches Problem?

  2. 1000 Städte in optimaler Reihenfolge besuchen: Welcher Mensch hat in der Praxis ein solches Problem?

    Vielleicht der in solchen Zusammenhängen gern als Beispiel heran gezogene Handlungsreisende… – Aber wenn es sich dabei um einen realen Geschäftsmann bzw. eine reale Geschäftsfrau handelt, wird er oder sie früher oder später von der optimalen Route abweichen, weil die übergeordnete Handlung, also der Zweck der Geschäftsreise eine Änderung erfordert.
    Aber bei Routenplaner-Software dürfte sich die Frage in ähnlicher Form stellen, etwa: “Wie kommt man am besten von Berlin nach München oder von Frankfurt/Main über Hannover nach Hamburg?”

    P.S. Hab ich eigntlich schon mal erwähnt, das die Captchas hier im HLF-Bereich reichlich schwierig sind? – Ja, jetzt gerade. 😉
    Wenn die so auch in den SciLogs eingeführt werden sollten, würde ich mir manchmal wahrscheinlich zweimal überlegen, ob ich einen Kommentar schreibe oder es sein lasse, weil die Captchas (zumindest der eine Teil) schwer zu entziffern ist.

Leave a Reply


E-Mail-Benachrichtigung bei weiteren Kommentaren.
-- Auch möglich: Abo ohne Kommentar. +