P vs. NP: Wie Forscher die letzte Frage der Informatik beantworten wollen
Ein 50 Jahre altes Problem der theoretischen Informatik – bekannt als P vs. NP – entzieht sich noch immer einer Lösung. Die könnte die IT-Geschichte ändern.
Das „Problem des Handlungsreisenden“ (Travelling Salesman) besteht darin, den kürzesten Weg zwischen n Städten zu finden und dabei keinen Weg zweimal zu benutzen.
(Bild: Derek Brahney)
- Siobhan Roberts
Montag, der 19. Juli 2021, war wieder einer dieser Tage. Ein Tag, mitten im zweiten Pandemie-Sommer, an dem anscheinend alles schiefgeht. Jedenfalls liest sich der Tweet eines führenden Informatikers so, der eigentlich auf dem Gebiet der Komplexitätstheorie forscht, sich nun aber heftig über den administrativen Schlamassel bei einer führenden Fachzeitschrift beklagt – und seinen Tweet mit einem sehr geladenen "Happy Monday" beendet. Dabei hätte dieser Tag vielleicht tatsächlich ein glücklicher Montag sein können – in irgendeinem Paralleluniversum. Denn an diesem Tag erschien in der Online-Ausgabe der angesehenen Fachzeitschrift "ACM Transactions on Computational Theory", die sich mit "herausragender Forschung zu den Grenzen machbarer Berechnungen" befasst, ein Paper, in dem angeblich eine Lösung für das Problem aller Probleme stand – dem Heiligen Gral der theoretischen Informatik.
Dieses Problem – bekannt als "P versus NP" – gilt als das wichtigste Problem der theoretischen Informatik. Für seine Lösung ist eine Prämie von einer Million Dollar ausgesetzt. Es befasst sich mit zentralen Fragen zu den Verheißungen, Grenzen und Ambitionen der Computertechnik: Welche Probleme können Computer realistischerweise lösen? Wie viel Zeit werden sie dafür benötigen? Und warum sind manche Probleme schwieriger als andere? Was heißt eigentlich "schwierig"?
"P" steht dabei für Probleme, die ein Computer leicht lösen kann
Die Angabe einer absoluten Zeit für Berechnungen ist wenig sinnvoll. Denn natürlich hängt die Geschwindigkeit einer Berechnung von der Rechenpower des Computers ab, zum anderen aber auch von der Größe des Problems selbst: Es dauert länger, eine Liste mit 1.000 Elementen zu sortieren als eine Liste mit 100 Elementen. Informatiker teilen Berechnungen also danach ein, wie die Rechenzeit mit der Anzahl der zu berechnenden Variablen ansteigt. "P" steht dabei für Probleme, die ein Computer leicht lösen kann. Präziser ausgedrückt steht P für "Polynomial". Das heißt, die Abhängigkeit der Berechnungszeit lässt sich als ein Polynom – die Summe von Potenzen – der Variablenzahl beschreiben. "NP" steht für "Nichtdeterministisch Polynomial". Das sind Probleme, die schwer zu lösen sind, bei den die Rechenzeit zum Beispiel exponentiell ansteigt. Gleichzeitig ist deren Lösung relativ einfach zu überprüfen: Solche Berechnungen funktionieren wie Falltüren oder Zahnräder mit Sperrhaken: In eine Richtung lassen sie sich leicht bewegen, in die andere nur gegen einen extremen Widerstand. Man nimmt eine mögliche Lösung und rechnet nach, ob sie wirklich funktioniert – wie bei Puzzles oder Sudoku-Rätseln.
Das klingt sehr abstrakt, aber viele NP-Probleme sind technisch und wissenschaftlich sehr relevant – wie die Frage, in welche Primfaktoren sich eine Zahl zerlegen lässt. Auf der Tatsache, dass der Rechenaufwand für dieses Problem mit der Größe dieser Zahl exponentiell anwächst, beruhen große Teile der Verschlüsselung im Internet. Die Millionen-Dollar-Frage, die sich bei P vs. NP stellt, ist folgende: Sind diese beiden Klassen von Problemen ein und dasselbe? Das heißt, könnten die Probleme, die so schwierig erscheinen, tatsächlich mit einem Algorithmus in einer vernünftigen Zeitspanne gelöst werden – zumindest im Prinzip? Wenn nur der richtige, teuflisch schnelle Algorithmus gefunden werden könnte?
Gigantische Chancen, wenn P=NP
Wäre P=NP, könnte früher oder später jemand eine Lösung für die Primzahlzerlegung finden, und damit die gesamte Kryptosphäre auseinanderreißen – ganz ohne Quantencomputer. Aber es gäbe auch gigantische Chancen: Die Proteinfaltung, eine 50 Jahre alte große Herausforderung in der Biologie, würde leichter zu bewältigen sein und damit völlig neue Möglichkeiten zur Entwicklung von Medikamenten zur Heilung oder Behandlung von Krankheiten und zur Entdeckung von Enzymen für den Abbau von Industrieabfällen eröffnen. Das würde auch bedeuten, dass man optimale Lösungen für schwierige Alltagsprobleme finden könnte, wie zum Beispiel die Planung einer Autoreise, um alle Ziele mit möglichst wenig Fahrzeit zu erreichen, oder die Sitzordnung für Hochzeitsgäste, sodass nur Freunde am selben Tisch sitzen.
(Bild: The University of Toronto)
Seit das P-vs.-NP-Problem vor rund 50 Jahren zum ersten Mal formuliert wurde, haben Forscher auf der ganzen Welt versucht, eine Lösung zu finden. Doch selbst Stephen Cook von der University of Toronto, der mit einer bahnbrechenden Arbeit im Jahr 1971 den Grundstein für das Gebiet der Computerkomplexität legte, war mit seiner Suche überfordert. Für seine Arbeit erhielt er zwar den Turing Award, das Äquivalent zum Nobelpreis in der Informatik. Aber auch Cook gesteht ein, er habe nie eine gute Idee gehabt, wie man das Problem knacken könnte – "es ist einfach zu schwierig".
