P-NP-Problem einfach erklärt: P, NP und Reduktion

Die Komplexitätstheorie fragt, wie schnell der Aufwand eines Problems mit der Größe der Eingabe wächst. Beim Sortieren von Karteikarten ist die Größe der Eingabe zum Beispiel die Anzahl der Karteikarten. Ein Entscheidungsproblem hat als Antwort nur „Ja“ oder „Nein“.

Die Klasse P enthält die Entscheidungsprobleme, die eine deterministische Turingmaschine in Polynomialzeit löst. „Deterministisch“ heißt: Der Rechenweg ist immer eindeutig bestimmt. „Polynomialzeit“ heißt: Es gibt ein Polynom wie f(n)=n^{k}+c mit natürlichen Zahlen c und k, das die Zahl der Rechenschritte für jede Eingabe der Länge n nach oben beschränkt.

Die Klasse NP enthält die Entscheidungsprobleme, bei denen es für „Ja“-Antworten Beweise gibt, die sich in Polynomialzeit verifizieren lassen. Es kann aber aufwändig sein, einen solchen Beweis zu finden. Ein Beispiel: Derzeit ist kein deterministischer Algorithmus bekannt, der eine gegebene Zahl in Polynomialzeit faktorisiert. Es ist jedoch sehr einfach prüfbar, ob ein vorgeschlagener Faktor die Zahl ohne Rest teilt.

NP lässt sich gleichwertig über die nichtdeterministische Turingmaschine (NTM) beschreiben. Sie kann in einer Situation mehrere Möglichkeiten haben, ihre Berechnung fortzusetzen. Das ist nur ein theoretisches Modell, denn es gibt keine real existierenden Computer, die ihren Rechenweg derart verzweigen können.

Eine deterministische Turingmaschine ist ein Spezialfall der NTM. Darum ist P eine Teilmenge von NP. Ein häufiger Irrtum ist, NP für die Klasse der Probleme zu halten, die sich nicht in Polynomialzeit lösen lassen. NP legt aber lediglich eine obere Schranke fest und enthält auch alle Probleme aus P.

Beim Problem des Handlungsreisenden (englisch Traveling Salesman Problem, kurz TSP) werden mehrere Orte nacheinander besucht. Keine Station außer der ersten darf mehr als einmal vorkommen, die erste Station ist gleich der letzten, und die gesamte Strecke soll möglichst kurz sein. Das ist ein Optimierungsproblem: Gesucht ist die beste Lösung.

Man modelliert es als Graphen. Die Knoten sind die Städte, jede Kante zwischen zwei Knoten hat eine Länge, die zum Beispiel als Strecke, Reisezeit oder Kosten gelesen werden kann. Eine Tour ist ein Kreis, der jeden Knoten genau einmal enthält. Gesucht ist eine möglichst kurze Tour.

NP-Vollständigkeit ist formal nur für Entscheidungsprobleme definiert. Deshalb macht man aus der Optimierung eine Ja-Nein-Frage. Statt „Wie kurz ist die kürzeste Rundreise?“ fragt die Entscheidungsversion: Gibt es durch die gegebenen Städte eine Rundreise, deren Länge eine gegebene Grenze nicht überschreitet? Für Optimierungs- und Suchprobleme spricht man von NP-Äquivalenz. Umgangssprachlich sagt man trotzdem oft „NP-vollständig“. Das ist möglich, da verschiedene Problemtypen ineinander überführbar sind.

Wende die Definition von NP auf diese Frage an: Ein Zertifikat wäre eine vorgeschlagene Rundreise. Ob sie jede Stadt genau einmal besucht und ob ihre Länge die Grenze nicht überschreitet, lässt sich durch Nachrechnen der Streckenlängen prüfen. Das ist eine Anwendung der allgemeinen Definition, keine feste Regel zum Auswendiglernen.

Die Bestimmung guter Lösungen ist beim TSP vergleichsweise leicht, das Finden einer beweisbar optimalen Lösung ist sehr schwierig. Hat man einen Rechner, der die Lösung für 30 Städte in einer Stunde berechnet, dann braucht dieser für zwei zusätzliche Städte annähernd die tausendfache Zeit; das sind mehr als 40 Tage.

Eine Polynomialzeitreduktion (auch polynomielle Reduktion) führt ein Entscheidungsproblem L auf ein Entscheidungsproblem L' zurück. Dafür braucht man eine Funktion f, die in polynomieller Zeit berechenbar ist. Für jedes Wort w muss gelten: w liegt in L genau dann, wenn f(w) in L' liegt. Ja-Antworten bleiben also Ja-Antworten, Nein-Antworten bleiben Nein-Antworten.

Ein Problem X ist NP-schwer, wenn man jedes Problem in NP durch Polynomialzeitreduktion auf X reduzieren kann. Ein Problem ist NP-vollständig, wenn es in NP liegt und NP-schwer ist. Es gehört damit zu den schwierigsten Problemen in NP.

So weist man NP-Vollständigkeit nach: Die erste Eigenschaft ist in aller Regel einfach. Man „rät“ eine Lösung und zeigt, dass man in Polynomialzeit verifizieren kann, ob sie wirklich zutrifft. Für die zweite Eigenschaft nimmt man gewöhnlich ein ähnliches Problem, dessen NP-Vollständigkeit schon bekannt ist, und reduziert es auf das neue Problem. Wegen der Transitivität von Polynomialzeitreduktionen sind dann alle Probleme aus NP auf das neue Problem reduzierbar.

Den Begriff der NP-Vollständigkeit führte 1971 Stephen A. Cook ein. Er zeigte, dass das Erfüllbarkeitsproblem der Aussagenlogik NP-vollständig ist. Richard Karp wies 1972 mit der Technik der Polynomialzeitreduktion für weitere 21 populäre Probleme die NP-Vollständigkeit nach.

Was NP-vollständig bedeutet, deutest du vorsichtig: Solche Probleme lassen sich vermutlich nicht effizient lösen. Das ist eine Vermutung, kein Beweis. Für viele NP-vollständige Probleme gibt es Lösungsverfahren, mit denen sie für in der Praxis auftretende Größenordnungen in akzeptabler Zeit lösbar sind.

Nicht jedes Problem in NP ist NP-vollständig. Das Graphisomorphieproblem (die Frage, ob zwei Graphen zueinander isomorph sind) liegt in NP. Man weiß nicht, ob es NP-vollständig ist. Falls P ≠ NP gilt, ist es ein Kandidat für ein Problem, das weder in P liegt noch NP-vollständig ist.

Die P-NP-Frage lautet: Sind die Menge der schnell lösbaren Probleme (P) und die Menge der schnell prüfbaren Probleme (NP) identisch? Dass alles schnell Lösbare auch schnell prüfbar ist, ist offensichtlich. Die Gegenrichtung ist nicht klar. Die Frage ist bis heute ungelöst. Erkannt wurde sie zu Beginn der 1970er Jahre durch unabhängige Arbeiten von Stephen Cook und Leonid Levin. Das Clay Mathematics Institute hat sie in die Liste der Millennium-Probleme aufgenommen.

Wenn ein einziges NP-vollständiges Problem für alle Eingaben in Polynomialzeit lösbar wäre, wäre jedes Problem in NP in Polynomialzeit lösbar, weil man es per Reduktion auf dieses Problem zurückführen könnte. Dann gälte P = NP. Für P ≠ NP müsste dagegen für ein Problem aus NP bewiesen werden, dass kein deterministischer Polynomialzeitalgorithmus es löst. Bisher ist keins von beidem gelungen. Der Großteil der Fachwelt vermutet P ≠ NP.

Sehr viele praktisch relevante Probleme sind NP-vollständig, zum Beispiel das Problem des Handlungsreisenden, das Rucksackproblem oder die Färbung von Graphen. Im Fall P = NP wären sie theoretisch optimal in kurzer Zeit lösbar. Allerdings könnten die Exponenten und Konstanten eines Polynomialverfahrens so hoch sein, dass für praktisch relevante Anwendungen ein bisher bekanntes Verfahren, zum Beispiel ein approximatives oder probabilistisches, immer noch das bessere ist. Große Bedeutung für die Praxis könnte P = NP haben, muss es aber nicht.

Auch die Kryptologie ist betroffen. Die Sicherheit einiger asymmetrischer Verschlüsselungsverfahren basiert allein auf dem Aufwand, sie zu brechen. Ein Beweis von P = NP würde bedeuten, dass die Aussicht besteht, diese Kryptosysteme in der Praxis zu brechen.

Mit einem Beweis von P ≠ NP wären NP-Probleme endgültig als schwer lösbar klassifiziert. Das entspricht derzeit der Annahme der meisten Wissenschaftler, und dieser Beweis wäre weniger folgenschwer als der Beweis von P = NP.