Wikipedia · einfach zusammengefasst · Stand
P-NP-Problem
Das P-NP-Problem (auch P≟NP oder P versus NP) ist ein ungelöstes Problem der Komplexitätstheorie in der theoretischen Informatik.
Inhalt5 Abschnitte
Kernfrage und Einordnung
Das P-NP-Problem (auch P≟NP oder P versus NP) ist ein ungelöstes Problem der Komplexitätstheorie, einem Gebiet der theoretischen Informatik. Es fragt, ob alle Probleme, deren vorgeschlagene Lösung schnell überprüft werden kann, auch schnell lösbar sind. „Schnell“ bedeutet dabei nicht unbedingt wenige Schritte, sondern: Es gibt einen Algorithmus, dessen Zahl der Rechenschritte mit der Eingabegröße höchstens polynomial wächst.
Die Eingabegröße ist vereinfacht die Zahl der eingegebenen Elemente, etwa die Anzahl von Karteikarten beim Sortieren. Die Komplexitätstheorie ordnet berechenbare Probleme danach, wie Zeit- oder Speicheraufwand mit der Problemgröße wachsen. Hier wird insbesondere die Zeitkomplexität, also die Zahl der Rechenschritte, betrachtet. Als formales Maschinenmodell dient häufig die deterministische Turingmaschine, die einen realen Computer abstrakt beschreibt.
Sicher gilt P ⊆ NP: Kann ein Problem schnell gelöst werden, kann man eine gefundene Lösung auch schnell überprüfen. Unklar ist die umgekehrte Richtung. Für manche Probleme lassen sich vorgeschlagene Lösungen effizient prüfen, doch es ist weder ein effizienter Lösungsalgorithmus gefunden noch seine Unmöglichkeit bewiesen. Ein Algorithmus für alle NP-Probleme mit polynomial beschränkter Laufzeit ergäbe P = NP. Ein Beweis, dass mindestens ein NP-Problem prinzipiell nicht schnell lösbar ist, ergäbe P ≠ NP.
Die Klasse P
P ist die Klasse der Probleme, die eine deterministische Turingmaschine in Polynomialzeit löst. Genauer gibt es ein Polynom f(n)=n^k+c mit c,k ∈ ℕ, sodass die Maschine für jede Probleminstanz x höchstens f(n) Rechenschritte benötigt; dabei ist n=len(x), also die Länge der Eingabe. Probleme in P sind damit deterministisch in Polynomialzeit lösbar.
Das Sortieren von n Datensätzen beziehungsweise Karteikarten gehört zu P, weil Algorithmen existieren, deren Laufzeit durch eine quadratische Funktion in n beschränkt ist. Auch das Schaltkreis-Auswertungsproblem ist in P. Dass reale Computer und Turingmaschinen verschieden sind, ändert die Einordnung nicht: Ein auf einem realen Rechner polynomialzeitlicher Algorithmus kann auch auf einer Turingmaschine in polynomialer Zeit umgesetzt werden, meist mit einem höheren Grad des Laufzeitpolynoms.
Die Klasse NP und vollständige Probleme
NP lässt sich mit einer nichtdeterministischen Turingmaschine (NTM) definieren. Eine NTM darf bei einem Berechnungsschritt mehrere mögliche Fortsetzungen haben; ihr Rechenweg ist daher nicht eindeutig. Sie ist ein theoretisches Modell, keine real existierende Maschine. NP ist die Menge der Probleme, die eine NTM in Polynomialzeit lösen kann. Da eine deterministische Turingmaschine ein Spezialfall ohne Verzweigung ist, gilt P ⊆ NP.
Gleichbedeutend besteht NP aus Problemen, bei denen eine deterministische Turingmaschine in Polynomialzeit entscheiden kann, ob eine vorgeschlagene Lösung zutrifft. Für das Faktorisieren einer gegebenen Zahl ist derzeit kein deterministischer Polynomialzeitalgorithmus bekannt. Ein vorgeschlagener Faktor lässt sich aber einfach prüfen, indem man testet, ob er die Zahl ohne Rest teilt.
NP-schwer heißt ein Problem X, wenn jedes Problem aus NP durch eine Polynomialzeitreduktion auf X zurückgeführt werden kann. Eine solche Reduktion übersetzt ein Problem effizient in ein anderes. Wäre ein NP-schweres X deterministisch in Polynomialzeit lösbar, wären dadurch alle NP-Probleme so lösbar und P = NP wäre gezeigt. Ein Problem heißt NP-vollständig, wenn es selbst in NP liegt und NP-schwer ist.
Typische NP-vollständige Probleme sind das Rucksackproblem und das Erfüllbarkeitsproblem der Aussagenlogik. Beim Rucksackproblem soll ein Behälter begrenzter Größe mit einer Auswahl vorgegebener Gegenstände so gefüllt werden, dass der Inhalt möglichst wertvoll ist, ohne die Kapazität zu überschreiten. Falls P ≠ NP gilt, gibt es nach dem Satz von Ladner außerdem NP-Probleme, die weder in P noch NP-vollständig sind. Das Graphen-Isomorphismus-Problem ist ein Kandidat: Bisher ist weder bekannt, ob es in P liegt, noch ob es NP-vollständig ist.
Stand der Lösung und Grenzen von Beweisen
Zum exakten Lösen NP-vollständiger Probleme sind auf deterministischen Rechenmaschinen bisher nur Exponentialzeitalgorithmen bekannt. Das beweist jedoch nicht, dass es keine polynomialzeitlichen Algorithmen gibt. EXPTIME-vollständige Probleme benötigen dagegen garantiert mindestens exponentielle Laufzeit und liegen damit beweisbar außerhalb von P.
Die Fachwelt vermutet überwiegend P ≠ NP. Mögliche Ergebnisse wären ein Beweis von P ≠ NP, ein Beweis, dass P ≠ NP logisch unabhängig von ZFC ist, oder ein Beweis von P = NP – entweder durch einen effizienten Algorithmus für ein NP-vollständiges Problem oder nicht-konstruktiv ohne expliziten Algorithmus.
Bestimmte Beweismethoden reichen für sich nicht aus. Relativierende Beweise bleiben auch dann gültig, wenn ein beliebiges Orakel A als zusätzliche Rechenhilfe zugelassen wird. Der Satz von Theodore Baker, John Gill und Robert Solovay zeigt jedoch: Es gibt zwei Orakel A und B mit P^A=NP^A und P^B≠NP^B. Daher können relativierende Techniken wie Diagonalisierung das P-NP-Problem nicht entscheiden.
Auch „natürliche Beweise“, eingeführt 1994 von Alexander Alexandrowitsch Rasborow und Steven Rudich, haben unter der vermuteten Annahme bestimmter Einwegfunktionen eine Grenze: Mit einer bestimmten Sorte kombinatorischer Techniken lassen sich P und NP nicht trennen. Vereinfacht definiert ein solcher Beweis ein für ausreichend viele Funktionen geltendes und ausreichend einfach überprüfbares Kriterium der „Einfachheit“, das P-Funktionen besitzen, ein NP-vollständiges Problem aber nicht.
Bedeutung und historische Einordnung
Das Problem wurde Anfang der 1970er Jahre unabhängig durch Stephen Cook und Leonid Levin erkannt und gehört zu den Millennium-Problemen des Clay Mathematics Institute. Frühere Formulierungen finden sich in einem Brief von Kurt Gödel an John von Neumann vom 20. März 1956 sowie in einem Brief von John Forbes Nash von 1955 an die National Security Agency zur Kryptographie.
Viele praktisch wichtige Probleme sind NP-vollständig, darunter das Problem des Handlungsreisenden, das Rucksackproblem und das Färben von Graphen. Bei P = NP wären sie theoretisch optimal in kurzer Zeit lösbar. Hohe Exponenten oder Konstanten eines polynomialen Verfahrens könnten aber dazu führen, dass bekannte approximative oder probabilistische Verfahren praktisch weiterhin besser sind. Ein Beweis von P ≠ NP würde NP-Probleme endgültig als schwer lösbar klassifizieren; dies entspricht der gegenwärtigen Annahme der meisten Wissenschaftler.
Für die Kryptologie ist schwere Lösbarkeit erwünscht. Die Sicherheit einiger asymmetrischer Verschlüsselungsverfahren beruht darauf. Ein NP-Algorithmus könnte einen geheimen Schlüssel erraten, eine Nachricht effizient entschlüsseln und den Schlüssel dadurch verifizieren. P = NP eröffnete daher die Aussicht, solche Systeme praktisch zu brechen. Außerdem hängt die Frage mit Einwegfunktionen zusammen: Falls diese existieren, folgt P ≠ NP.
Zahlreiche behauptete Beweise wurden veröffentlicht, aber keine Lösung ist allgemein anerkannt. Gerhard Woegingers Sammlung enthielt im September 2016 unter anderem 62 angebliche Beweise für P=NP und 50 für P≠NP. Als fachlich akzeptiert gilt dort nur eine Arbeit von Mihalis Yannakakis; sie entscheidet die Frage nicht, sondern zeigt, dass ein bestimmter Lösungsansatz nicht funktionieren kann. Das P-NP-Problem bleibt ungelöst.
