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

Die Eingabegröße $n$ beschreibt, wie groß eine Problemangabe ist, etwa wie viele Städte eine Routenaufgabe enthält. Ein Algorithmus arbeitet in Polynomialzeit, wenn seine Zahl an Rechenschritten für ein festes $k$ durch einen Ausdruck wie $n^k+c$ begrenzt ist. Typische Laufzeiten sind $O(n)$, $O(n^2)$ oder $O(n^5)$.

Bei $f(n)=3n^2+2n+1$ dominiert für große $n$ der quadratische Term. Deshalb schreibt man $f(n)\in O(n^2)$. Dagegen ist $O(2^n)$ exponentiell: Erhöht sich $n$ um eins, verdoppelt sich der führende Wert.

In der formalen Theorie betrachtet man Entscheidungsprobleme: Zu jeder Eingabe lautet die Antwort Ja oder Nein.

Ein Zertifikat ist die mitgelieferte Information, die eine Ja-Antwort belegt. Wer das Zertifikat prüft, muss es nicht selbst finden.

Es gilt sicher $P\subseteq NP$: Ein Prüfer kann bei einem Problem aus P das Zertifikat ignorieren und die Ja-Nein-Frage selbst in Polynomialzeit entscheiden. Offen ist, ob auch $NP\subseteq P$ gilt.

Beim SAT-Problem ist eine aussagenlogische Formel gegeben. Gefragt wird: Gibt es eine Belegung der Variablen mit wahr oder falsch, sodass die gesamte Formel wahr wird?

Auch das Problem des Handlungsreisenden lässt sich als Entscheidungsproblem formulieren: „Gibt es eine Rundreise, die jede Stadt genau einmal besucht und höchstens $L$ Kilometer lang ist?“ Ein Zertifikat ist eine konkrete Rundreise. Zur Prüfung kontrollierst du die Besuche, addierst die Streckenlängen und vergleichst die Summe mit $L$.

Das ist nicht dasselbe wie die Behauptung, die Route sei global die kürzeste. Die Prüfung gegen eine vorgegebene Grenze belegt nur: Es gibt eine zulässige Route bis $L$.

Formuliere selbst eine Entscheidungsfrage

Beim Rucksackproblem sind Gegenstände mit Gewicht und Wert gegeben. Der Rucksack darf höchstens das Gesamtgewicht $G$ tragen. Formuliere eine Ja-Nein-Frage, die zusätzlich den Zielwert $W$ verwendet.

Eine polynomielle Reduktion von Problem A auf Problem B ist eine in Polynomialzeit berechenbare Umformung. Sie übersetzt jede Instanz von A in eine Instanz von B, wobei die Ja-Nein-Antwort erhalten bleibt.

Schreibt man „A reduziert auf B“, dann gilt: Könnte man B polynomial lösen, könnte man zuerst A in B umformen und anschließend B lösen. Damit wäre auch A polynomial lösbar.

Warum ist das so wichtig? Angenommen, ein NP-vollständiges Problem X läge in P. Dann könnte man jedes Problem aus NP polynomial auf X reduzieren und X polynomial lösen. Also wäre $NP\subseteq P$. Zusammen mit $P\subseteq NP$ folgte $P=NP$.

Für $P=NP$ würde schon ein Polynomialzeitalgorithmus für ein einziges NP-vollständiges Problem genügen. Ein solcher Algorithmus könnte konstruktiv zeigen, wie sich alle NP-Probleme über Reduktionen polynomial lösen lassen.

Für $P\ne NP$ müsste bewiesen werden, dass mindestens ein Problem aus NP keinen deterministischen Polynomialzeitalgorithmus besitzt. Dass jahrzehntelang kein solcher Algorithmus gefunden wurde, stützt die verbreitete Vermutung $P\ne NP$, ist aber kein Beweis.

Das P-NP-Problem ist weiterhin offen. Es gehört zu den Millennium-Problemen; für eine anerkannte Lösung ist ein Preis von einer Million US-Dollar vorgesehen.

Falls $P=NP$ gilt, existieren für alle Probleme aus NP Polynomialzeitalgorithmen. Das wäre für Planung, Optimierung und automatisches Schlussfolgern grundlegend. Es würde auch kryptographische Verfahren gefährden, deren Sicherheit auf der Schwierigkeit passender Suchprobleme beruht.

Doch aus $P=NP$ folgt nicht automatisch ein sofort einsetzbarer Turbo-Algorithmus. Die garantierte Laufzeit könnte etwa einen sehr hohen Polynomgrad oder große Konstanten haben. Theoretische Effizienz und praktische Brauchbarkeit sind verschieden.

Falls $P\ne NP$ gilt, gibt es mindestens ein Entscheidungsproblem, dessen Ja-Zertifikate polynomial prüfbar sind, das aber nicht deterministisch in Polynomialzeit lösbar ist. Das würde eine grundlegende Grenze effizienter Berechnung beweisen. Es würde jedoch nicht pauschal die Sicherheit jedes konkreten Kryptosystems garantieren.