Für Mathematiker verbirgt sich hinter dem Kürzel "P=NP?" eine der aufregendsten Fragen der Gegenwart. Bis zu den Laien ist sie nur in Ausnahmefällen vorgedrungen; "Chaostheorie" oder "Katastrophentheorie" fanden schon leichter den Weg aus dem Elfenbeinturm, vermutlich deswegen, weil diese Wörter an Bekanntes anknüpfen - ganz im Gegensatz übrigens zu den dahinterstehenden Theorien.

"P=NP?" sieht nicht sehr attraktiv aus. Das Problem ist aber von mindestens ebenso grundsätzlicher Bedeutung: Es betrifft die prinzipiellen Grenzen unserer intellektuellen Möglichkeiten - und hat zugleich mit handfesten Fragen zu tun, etwa damit, ob Geheimcodes - 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 klargemacht werden, auf welche Typen von Problemen wir uns hier konzentrieren wollen. Dann wird gezeigt, wie man eine Hierarchie der Schwierigkeitsgrade von Problemen einführen kann: Es gibt in einem präzisen Sinn "einfache" und "schwierige" Probleme. Unter den schwierigen finden sich allerdings solche Probleme, die sich auf einfache reduzieren lassen - bisher weiß leider niemand, ob sie notwendigerweise einfach sind oder ob das pure Glückssache ist. Glück? Doch, das gibt es in der Mathematik. Ein Geheimcode zum Beispiel ist oft nur mit viel Glück zu knacken, nämlich wenn wir den Schlüssel erraten. Doch was wir wirklich wissen wollen, ist dies: Läßt sich der Code auch ohne Glück entschlüsseln, also mit Hilfe einer Vorschrift?

Wer es genauer wissen möchte, ist nun herzlich eingeladen, die relevanten Begriffe näher kennenzulernen. Beginnen wir mit den "einfachen" und den "schwierigen" Problemen. Wir betrachten fast nur solche mathematischen Probleme, zu deren Formulierung Zahlen vorgegeben werden und als deren Lösung wieder eine Zahl (oder eine der Antworten "ja" oder "nein") erwartet wird. Es handelt sich also um Fragen wie "Was ist das Produkt von 324 mit 66 778?" oder "Ist 23 789 eine Primzahl?"; Fragen des Typs "Gibt es unendlich viele Primzahlen?" werden hier also keine Rolle spielen.

In den sechziger Jahren fingen die Mathematiker an, sich darüber Gedanken zu machen, ob sie die vage Vorstellung von einfachen und schwierigeren Problemen präzisieren könnten, und sie fanden einen Ansatz, der sich als sehr erfolgreich erwiesen hat. Zunächst ist so etwas wie eine Normierungsvorschrift vonnöten, damit wirklich nur das Vergleichbare verglichen wird. Wer beispielsweise behauptet, daß Quadrieren schwieriger ist als Verdoppeln, der sollte das nicht gerade an den Beispielen 122 und 2 6 785 389 erläutern. Als Fairneßbedingung vereinbaren wir daher, jeweils nur Probleme gleicher Komplexität miteinander vergleichen zu wollen, und als Maß der Komplexität soll die Anzahl derjenigen Ziffern gelten, die nötig ist, um das Problem zu formulieren.

Jetzt können wir sagen, warum Quadrieren schwieriger ist als Verdoppeln: Um eine k-stellige Zahl 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 (oder mit einer "Laufzeit") aus, die zu k proportional ist. Bei der klassischen Methode des Quadrierens hingegen muß ich jede Ziffer der Zahl mit jeder andern Ziffer multiplizieren, 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 k2-mal. Bei verwickelteren Problemen können auch noch mehr, zum Beispiel k3, Einzeloperationen erforderlich sein.

Damit sind wir schon beim ersten wichtigen Teil des Kürzels "P=NP?": Ein Problem heißt "vom polynomialen Typ" oder kürzer "vom Typ P", wenn ein Verfahren bekannt ist, das die Lösung im Falle von k Eingangsziffern in höchstens kr 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 sowie r=2). Wir dürfen, allgemein gesprochen, ein Problem - genauer: ein Lösungsverfahren - als um so schwieriger ansehen, je größer das zugehörige r gewählt werden muß.