Probleme vom Typ "P" und "NP"

Ist Glück in der Mathematik entbehrlich?

Ehrhard Behrends

(Erschienen in der Wochenzeitschrift "DIE ZEIT" am 4. 3. 1999)

Für Mathematiker verbirgt sich hinter dem unanschaulichen Kürzel "P=NP?" eine der spannendsten bisher ungelösten Fragestellungen der Gegenwart, bis zu Laien ist sie allerdings nur in Ausnahmefällen vorgedrungen. "Chaostheorie" und "Katastrophentheorie" etwa fanden viel leichter den Weg aus dem Elfenbeinturm, sicher deswegen, weil diese Wörter an scheinbar Bekanntes anknüpfen.

Das ist schade, denn das Thema dieses Artikels ist eigentlich von noch grundsätzlicherer Bedeutung. Es betrifft die prinzipiellen Grenzen unserer intellektuellen Möglichkeiten und hat gleichzeitig mit handfesten konkreten Fragen zu tun, etwa damit, ob Geheimcodes - die von Kreditkarten zum Beispiel - wirklich so resistent gegen Entschlüsselung sind wie gemeinhin angenommen.

Es wird in diesem Artikel um das Lösen von mathematischen Problemen gehen. Zunächst soll an einigen Beispielen klar gemacht werden, auf welche Typen von Problemen wir uns hier konzentrieren wollen. Dann wird gezeigt, wie man - die Schwierigkeit der jeweiligen Lösung betreffend - eine Hierarchie einführen kann: es gibt in einem präzisen Sinn "einfache" und "schwierige" Probleme. Unter den scheinbar schwierigen gibt es allerdings solche, die man mit unglaublich viel Glück auf einfache reduzieren kann. Und heute weiß niemand, ob sie dann notwendig wirklich einfach sind. Offensichtlich ist zum Beispiel ein Geheimcode mit viel Glück zu knacken, man braucht ja "nur" die Geheimzahl richtig zu raten. Die Auswirkungen sind leicht vorstellbar, wenn gezeigt werden könnte, daß es dann auch ein Verfahren ohne Glücks-Anteil geben muß.

Soweit die notwendig noch recht vage Übersicht. Wer es genauer wissen möchte, ist nun herzlich eingeladen, die relevanten Begriffe etwas näher kennenzulernen.

"Einfache" und "schwierige" Probleme

Es wird hier ganz handfest zugehen. Wir betrachten fast nur solche mathematischen Probleme, bei denen zur Formulierung Zahlen vorgegeben werden und bei denen als Lösung wieder eine Zahl (oder eine der Antworten "ja" oder "nein") erwartet wird. Man denke an so etwas Vertrautes wie "Was ist das Produkt von 324 mit 66778?" oder "Ist 23789 eine Primzahl?"; Fragen des Typs "Gibt es unendlich viele Primzahlen?" werden hier also keine Rolle spielen. Als einziges etwas komplizierteres Problem möchte ich das Problem des Handlungsreisenden erwähnen, bei dem Städte und Entfernungen vorgegeben sind und bei dem man eine (möglichst) kurze Route durch alle diese Städte sucht (siehe Kasten).

In den sechziger Jahren fing man nun an, sich darüber Gedanken zu machen, ob man nicht die vage Vorstellung von einfachen und schwierigeren Problemen präzisieren könnte. Am Beginn steht so etwas wie eine Normierungsvorschrift, damit wirklich nur vergleichbare Situationen gleichzeitig betrachtet werden. Wenn man also behauptet - was jeder noch aus der Schulzeit weiß - daß Quadrieren schwieriger ist als Verdoppeln, so sollte man das nicht gerade an den Beispielen 12² und 2·6785389 erläutern. Als Fairneßbedingung vereinbaren wir, daß wir jeweils nur Probleme gleicher Komplexität miteinander vergleichen wollen, und die Komplexität soll die Anzahl derjenigen Ziffern sein, die man braucht, um das Problem zu stellen. Jetzt können wir sagen, warum Quadrieren schwieriger ist: Um eine k-stellige Zahlen zu verdoppeln (Komplexität der Eingabe: k) muß ich k-mal zwei Ziffern addieren und eventuell den Übertrag notieren, ich komme also mit einer Anzahl von Rechenschritten aus, die zu k proportional ist; bei der klassischen Methode der Multiplikation hingegen muß ich jede Ziffer der Zahl mit jeder andern Ziffer malnehmen, von den dann folgenden Additionen ganz zu schweigen. Anders ausgedrückt: Im ersten Fall muß ich - wenn ich von hier unwesentlichen Konstanten absehe - k-mal etwas tun, im zweiten k²-mal. Bei verwickelteren Problemen können auch noch mehr, z. B. k³ Einzeloperationen erforderlich sein.

Damit sollte der erste wichtige Begriff hinreichend motiviert sein: Ein Problem heißt vom polynomialen Typ oder kürzer vom Typ P, wenn ein Verfahren bekannt ist, das einem die Lösung im Falle von k Eingangsziffern in höchstens k^r Rechenschritten liefert. Dabei darf r irgendeine natürliche Zahl sein, die nicht von den konkreten Ziffern abhängt. Wir haben gerade gesehen, daß Verdoppeln und Quadrieren vom Typ P sind (mit r = 1 bzw. r = 2). Sicher wird man allgemeiner ein Problem - genauer: ein Lösungsverfahren - als schwieriger ansehen, wenn das zugehörige r größer ist.

Die meisten Probleme, die man in der Schule kennenlernt, sind vom Typ P. Addieren, Multiplizieren, Wurzeln ziehen, Potenzen bilden, Gleichungssysteme lösen usw. Dabei ist es durchaus noch Gegenstand aktueller Forschung, Lösungsverfahren zu verbessern und nach Möglichkeit zu optimieren. Nehmen wir als Beispiel das alphabetische Sortieren von k Visitenkarten. Die meisten würden das doch so machen, daß sie zunächst die Karte raussuchen, für die der zugehörige Name am weitesten vorn im Alphabet steht, das sind k Aktionen. Dann wird das mit dem Rest noch einmal gemacht, weitere k-1 Handlungen sind erforderlich. Am Ende hat man 1+2+¼+k = k(k+1)/2 Mal eine Visitenkarte in der Hand gehabt. Da k(k+1)/2 durch k² abschätzbar ist, ist Sortieren als Problem vom Typ P mit dem Exponenten r = 2 erkannt. Bemerkenswerterweise kann man es aber geschickter machen und den Exponenten beinahe auf r = 1 drücken. (Für alle, die noch wissen, was ein Logarithmus ist: Es gibt Sortierverfahren, die eine Laufzeit-Größenordnung klogk haben, und das ist fast so gut wie k¹. Man weiß außerdem, daß bessere Verfahren nicht möglich sind.) Das hat erhebliche Auswirkungen, da Sortieren in vielen Computer-Anwendungen eine fundamentale Rolle spielt.

Wie steht es aber mit dem Problem: "Finde einen Teiler einer vorgelegten k-stelligen Zahl z, von der bekannt ist, daß sie keine Primzahl ist"? Das übliche Verfahren sieht doch so aus: Teste systematisch alle Kandidaten von 2 bis zur Wurzel aus z, ob sie in z aufgehen. Das sind bei einer k-stelligen Zahl im wesentlichen 10^k/2 Rechenoperationen, und das ist eine viel höhere Größenordnung als k^r, egal, wie wir r festlegen. (Genau genommen sagt dieses Argument nur, daß durch das beschriebene Verfahren - und übrigens auch durch alle anderen heute bekannten - nicht klar wird, ob es sich um ein Typ-P-Problem handelt. Vielleicht kommt in 10 Jahren jemand auf eine Methode, bei der k² Rechenschritte ausreichen.)

Alle Probleme vom Typ P wollen wir als "einfache" Probleme ansehen. Der Grund ist der, daß sie selbst bis zu eindrucksvollen Größenordnungen (also auch für größere Komplexität k) relativ leicht mit Computer-Hilfe gelöst werden können. Nicht einfach in diesem Sinn ist nach dem derzeitigen Wissensstand das Teiler-Findungsproblem. Und das ist gut so, es handelt sich um eine wesentliche Grundlage unseres Wirtschaftssystems, da viele kryptographische Verfahren genau darauf beruhen (Verschlüsselung im Internet, Banken-Transfers usw.). Ebenfalls schwierig ist heute das Problem des Handlungsreisenden, dazu kommt ein unübersehbare Schar von anderen Beispielen.

Leider weiß man nur in weniger interessanten Fällen, daß es sich um wirklich schwierige Probleme handelt, also um solche, bei denen man garantieren kann, daß niemand, auch nicht in noch so ferner Zukunft, ein Lösungsverfahren mit Laufzeitabschätzung k^r finden kann. Ein Beispiel: Das Aufschreiben aller k-stelligen Zahlen, die man aus 3 und 7 bilden kann, erfordert sicherlich 2^k Aktionen, und da kann man sich beim besten Willen nicht wesentlich geschickter anstellen. Hier wären natürlich auch diejenigen Probleme zu nennen, die garantiert überhaupt nicht lösbar sind; Turings Halteproblem zum Beispiel oder Ergebnisse von Gödel über die Unmöglichkeit des Nachweises, eine widerspruchsfreie Grundlage der Mathematik zu schaffen. Wir wollen uns aber lieber um Konkreteres kümmern.

Glück

Unter den Problemen, die nach dem heutigen Wissensstand nicht vom Typ P sind, also unter denen, die wir als schwierig bezeichnet haben, gibt es nun viele, die man mit viel Glück dennoch schnell lösen kann. Wie sieht es etwa bei der Aufgabe aus: "Finde einen Teiler von 1050504368559379"? (Der Aufgabensteller garantiert, daß es Teiler gibt.) Bei einer systematischen Suche müßte man für jede Zahl bis zur Wurzel, also etwa dreißig Millionen Mal, einen Divisionsversuch starten. Mit Glück geht's aber schneller, man könnte ja einfach eine Zahl zwischen 2 und der Wurzel raten und hoffen, durch Zufall einen Teiler zu erwischen. Wenn man also - mit viel Glück - in unserem Beispiel die Zahl 18712789 rät und dann teilt, ist der Fall erledigt, denn es geht wirklich auf. Nachträglich wird verraten, daß 1050504368559379 = 18712789·56138311 mit den Primzahlen 18712789 und 56138311 ist. Das ist deswegen interessant, weil wir so die notwendige Intensität unseres Glücks abschätzen können: Nur wenn wir 18712789 raten, erhalten wir einen Teiler unterhalb der Wurzel, also nur in einem von dreißig Millionen Fällen. Die Wahrscheinlichkeit, es so zu schaffen, ist damit etwa ein Drittel von der Wahrscheinlichkeit für sechs Richtige im Lotto. Klar, daß man es etwas geschickter machen kann, an der Tatsache, daß die Erfolgswahrscheinlichkeiten winzig sind, ändert sich aber im Prinzip nichts.

Bei realistischen kryptographischen Problemen dieser Art treten übrigens viel größere Primzahlen auf, solche mit zweihundert Dezimalen sind durchaus Standard. Um da die Zahlen aus dem Produkt durch Raten zu rekonstruieren braucht man schon so viel Glück wie jemand, der dreißig Mal hintereinander sechs Richtige im Lotto hat. Und auch Computer würden da nicht weiter helfen: Auch für die schnellsten und größten Rechner würde die zur Verfügung stehende Zeit nicht ausreichen, selbst wenn man sie vom Urknall bis zum voraussichtlichen Ende unseres Sonnensystems durchrechnen lassen könnte.

Die meisten der interessanten Probleme, die wir heute als schwierig einschätzen, sind von dieser Art. Im Handlungsreisenden haben wir sofort ein zweites Beispiel: Möchte ich eine Route durch alle vorgegebenen Städte finden, bei der weniger als 1000 Kilometer zurückgelegt werden, so bekomme ich die - falls es eine gibt - auch durch Raten (natürlich auch nur mit unsagbar viel Glück, denn bei k Städten gibt es 1·2¼k mögliche Touren).

Man nennt Entscheidungsprobleme, die so behandelt werden können, Probleme vom Typ NP; das soll die Abkürzung für "nichtdeterministisch polynomial" sein. Etwas genauer: Man spricht dann von NP-Problemen, wenn sie im Falle der Lösbarkeit durch ein geeignetes Rateverfahren auf ein einfaches Problem (Typ P) zurückgeführt werden können. Auf die Fachtermini, mit denen man das präzisieren kann (nichtdeterministische Turingmaschine usw.) kann hier natürlich nicht eingegangen werden.

Ein Phänomen ist noch zu erwähnen, es gibt nämlich eine offensichtliche Asymmetrie in Bezug auf die NP-Frage zwischen einem Problem und der zugehörigen Negation. Gerade eben haben wir gesehen, daß es leicht ist, durch ein offensichtliches Verfahren eine Zahl als zusammengesetzt zu erkennen. Für das Gegenteil, also die Frage, ob eine Zahl eine Primzahl ist, ist das längst nicht so klar. Was soll man denn raten, um dann schnell die Primzahleigenschaft zu garantieren, schließlich sind doch alle kleineren Zahlen potentielle Teiler? In diesem Fall geht es allerdings doch, die für ein erfolgreiches Rateverfahren erforderlichen Informationen aus der Zahlentheorie würden uns aber hier zu weit vom Thema wegführen.

Ist Glück entbehrlich?

Im Zoo der Probleme gibt es also die einfachen und auch solche, die mit Glück zu einfachen werden. Da wir gesehen haben, daß der Begriff "Glück" dabei stark strapaziert wird, ist eigentlich nicht zu erwarten, daß die Probleme dann selbst schon einfach sein müßten. Zur Überraschung aller Mathematiker ist es jedoch skandalöserweise seit über dreißig Jahren nicht gelungen, auch nur ein einziges Problem zu finden, wo man das verifizieren könnte. Seit dieser Zeit sucht man also etwas, was beweisbar nicht vom Typ P aber dennoch vom Typ NP ist.

Es ist damit durchaus denkbar, daß morgen gezeigt wird: Alle NP-Probleme sind in Wirklichkeit schon einfach, Glück ist in der Mathematik entbehrlich. Niemand erwartet es ensthaft, es wäre eine echte Sensation, weil dann in hektischer Eile viele Verschlüsselungssysteme überarbeitet werden müßten. Ebenfalls spektakulär wäre der Nachweis, daß ein genügend relevantes NP-Problem garantiert nicht vom Typ P ist. Denn dann wären - mehr dazu gleich - sofort alle wichtigen Probleme mit Sicherheit ebenfalls nicht vom Typ P. Eine der nächsten Fieldsmedaillen, das sind die Nobelpreise für Mathematik, würde das Ergebnis mit Sicherheit einbringen, egal, ob es nun in der einen oder in der andern Richtung ausfällt.

NP-Vollständigkeit

Vielleicht sollte man die logische Struktur des hier anstehenden Problems noch einmal mit anderen Worten formulieren. Um zu zeigen, daß ein Problem vom Typ P ist, muß ich kreativ werden und so lange arbeiten, bis ich ein Lösungsverfahren gefunden habe, das - bei geeignetem, ein für allemal festem r - eine Laufzeit der Größenordnung k^r für Eingabe-Komplexität k hat. Der Nachweis des Gegenteils ist bei weitem schwieriger: Ein Problem ist nicht vom Typ P, wenn niemand, auch nicht der genialste Mathematiker in 10000 Jahren, ein Verfahren mit einer derart abschätzbaren Rechenzeit ersinnen kann.

Es könnte nun eigentlich auch noch so sein, daß man diese Schwierigkeit immer wieder neu bewältigen müßte. Hat also irgendjemand gezeigt, daß der Handlungsreisende wirklich schwierig ist, so muß das doch keine Auswirkungen für andere Fragestellungen haben. Daß das nicht so ist, wurde damals, als es 1971 von Cook bewiesen wurde, als kleine Sensation angesehen.

Cook betrachtete ein Problem aus der Logik. Man stelle sich als Beispiel drei Aussagen A,B,C vor und verknüpfe sie unter Verwendung von "und", "oder" und "nicht" zu einer neuen Aussage, zum Beispiel zu (A oder B) und (C oder nicht-B). Ist es dann möglich, A,B,C so die Wahrheitswerte "wahr" und "falsch" zuzuordnen, daß die neue Aussage nach den Regeln der Logik - die hier mit der Logik der täglichen Erfahrung völlig übereinstimmt - bei dieser Belegung den Wert "wahr" bekommt? Im Beispiel ist das leicht, das ist etwa für A,B,C = "wahr" der Fall.

Bei "vielen" logischen Variablen A,B,C,D,¼ und "langen" neuen Aussagen ist das jedoch nicht mehr so klar. Man müßte bei k Variablen 2^k Belegungen für die Wahrheitswerte testen, naiv ist das Problem sicher nicht in P. Sicher aber liegt es in NP, denn durch richtiges Raten von "wahr" und "falsch" kann ich eine zu "wahr" führende Belegung - wenn es überhaupt eine gibt - sicher finden. Soweit ist das nicht aufregend. Äußerst bemerkenswert ist jedoch eine weitere Eigenschaft: Jedes, auch das komplizierteste NP-Problem kann in ein derartiges Wahrheits-Belegungs-Problem umgeschrieben werden, ähnlich so, wie man eine Zahl in der Dezimaldarstellung in die Dualdarstellung einfach umschreiben kann.

Der Beweis ist, hat man ihn einmal verstanden, nicht einmal besonders kompliziert. Die Grundidee kann hier nur angedeutet werden. Zunächst ist festzusetzen, daß man unter einem Lösungsverfahren die Beschreibung eines Computerprogramms versteht, das die jeweilige Lösung in der geforderten Zeit auswirft. Und Cooks Idee besteht dann im wesentlichen darin, die erlaubten Computerprogramme als ziemlich lange Boolesche Ausdrücke zu codieren.

Die Konsequenzen sind erheblich, man braucht sich für die Beantwortung der Hauptfrage - ist P das gleiche wie NP? - nur noch auf das Cooksche Problem zu konzentrieren. Ist das nämlich nicht nur vom Typ NP sondern sogar vom Typ P, so sind alle NP-Probleme leicht.

Man spricht bei Problemen von derartiger Tragweite von NP-vollständigen Problemen. Das sind also NP-Probleme, bei denen der Nachweis, daß sie sogar vom Typ P sind, alle NP-Probleme zu einfachen machen würde. Heute kennt man hunderte von Beispielen für NP-Vollständigkeit, fast alle guten Bekannten sind dabei, etwa der Handlungsreisende. Genutzt hat es aber leider bisher nichts, trotz der vielen Möglichkeiten, nun nur noch für ein einziges Problem die P-Eigenschaft nachweisen zu müssen, hat noch keiner den Durchbruch geschafft.

Umgekehrt wäre es natürlich auch interessant: Weiß man für irgendein NP-vollständiges Problem, daß es beweisbar nicht vom Typ P ist, wären alle NP-vollständigen Probleme wirklich schwierig. Und erst dann könnten die Datenschützer wieder etwas ruhiger schlafen, denn dann wären sichere kryptographische Verfahren endlich greifbar nahe. Allerdings wäre trotzdem noch viel Arbeit zu leisten, denn bis heute ist es nicht gelungen, beweisbar NP-vollständige Probleme erfolgreich für das Verschlüsseln einzusetzen.