P-NP-Problem

Das P-NP-Problem (auch P≟NP, P versus NP) ist ein ungelöstes Problem der Mathematik und theoretischen Informatik, speziell der Komplexitätstheorie. Es stellt die Frage, in welcher Beziehung die beiden Komplexitätsklassen P und NP stehen. Erkannt wurde das Problem zu Beginn der 1970er-Jahre aufgrund unabhängig voneinander erfolgter Arbeiten von Stephen Cook und Leonid Levin.

Das P-NP-Problem gilt als eines der wichtigsten ungelösten Probleme der Informatik und wurde vom Clay Mathematics Institute in die Liste der Millennium-Probleme aufgenommen.

P und NP

Die Komplexitätsklasse NP, unter der Annahme P≠NP. In diesem Fall enthält NP auch Probleme oberhalb von P, die nicht NP-vollständig sind.^[1]

Die Komplexitätstheorie klassifiziert Probleme, die von Computern berechnet werden können, anhand des zu ihrer Lösung erforderlichen Aufwands. Eine Möglichkeit zur Quantifizierung des Berechnungsaufwands eines Algorithmus ist die Zahl der maximal notwendigen Rechenschritte, die Zeitkomplexität. Die Komplexität eines Problems ist dann die Komplexität des günstigsten Algorithmus, der dieses Problem löst und wird hierbei immer im Verhältnis zur Länge der Eingabe für die Berechnung angegeben. Zur exakten Analyse der Zeitkomplexität werden außerdem formale Maschinenmodelle benötigt. Ein häufig verwendetes Modell ist dabei die deterministische Turingmaschine, welche als die Abstraktion eines realen Computers angesehen werden kann.

Eine der komplexitätstheoretischen Problemkategorien ist die Komplexitätsklasse P. Zu jedem Problem dieser Klasse existiert eine deterministische Turingmaschine, welche das Problem löst und zu der ein Polynom der Form n^k angegeben werden kann, welches die Zeitkomplexität der Turingmaschine im Verhältnis zur Eingabelänge n nach oben beschränkt. Probleme aus P sind somit deterministisch in Polynomialzeit lösbar.

Beispiele für Probleme der Komplexitätsklasse P sind das Sortierproblem oder das Schaltkreis-Auswertungsproblem.

Eine weitere anhand der deterministischen Turingmaschine definierte Problemmenge ist die Komplexitätsklasse EXP. Anstelle eines Polynoms wird hier als obere Schranke für die Zeitkomplexität eine Funktion der Form 2ⁿ in Abhängigkeit von der Eingabelänge n angegeben. Die Lösung der schwersten Probleme dieser Klasse benötigt also exponentielle Zeit. Weiterhin ist die Klasse P vollständig in EXP enthalten. Für einige Probleme in EXP kann jedoch gezeigt werden, dass diese nicht in Polynomialzeit gelöst werden können, z. B. die Frage, ob eine Turingmaschine der Größe n auf einer Eingabe der Größe n innerhalb von 2ⁿ Schritten anhält oder nicht - das sogenannte Halteproblem. Die Lösbarkeit dieser Probleme kann nach derzeitigem Stand des Wissens auch durch zukünftige technologische Fortschritte nicht wesentlich verbessert werden.

Die Komplexitätstheorie definiert jedoch noch weitere Maschinenmodelle neben der deterministischen Turingmaschine. Ein wichtiges Modell ist die nichtdeterministische Turingmaschine, welche eine Erweiterung der deterministischen Variante darstellt. Eine nichtdeterministische Turingmaschine hat zu jedem Zeitpunkt potentiell mehrere Möglichkeiten, ihre Berechnung fortzusetzen, der Rechenweg ist deshalb nicht eindeutig bestimmbar. Es handelt sich dabei um ein theoretisches Modell, das nicht gleichwertig zu gegenwärtigen Computern ist. Sein Nutzen ist in diesem Zusammenhang, dass durch nichtdeterministische Turingmaschinen eine weitere Komplexitätsklasse unterschieden werden kann, welche innerhalb von EXP liegt und ihrerseits P einschließt.

Die Komplexitätsklasse NP ist die Menge aller von nichtdeterministischen Turingmaschinen in Polynomialzeit lösbaren Probleme. Diese Teilmenge von EXP enthält eine sehr große Zahl relevanter Problemstellungen. Da sich die Probleme aus P natürlich auch nichtdeterministisch in Polynomialzeit lösen lassen, ist P eine Teilmenge von NP. Unklar ist aber, ob die beiden Klassen identisch sind, und damit auch, ob die schwersten Probleme der Klasse NP ebenso effizient wie die der Komplexitätsklasse P gelöst werden können.

Ein anschauliches Problem aus NP, für das nicht klar ist, ob es in P enthalten ist, ist das Rucksackproblem. Bei diesem Problem soll ein Behälter einer bestimmten Größe so mit vorgegebenen Gegenständen gefüllt werden, dass der Behälter maximal gefüllt und der Inhalt so wertvoll wie nur möglich ist. Ein anderes wichtiges Beispiel ist das Erfüllbarkeitsproblem der Aussagenlogik.

Lösung des Problems

Bisher existieren zum exakten Lösen von NP-vollständigen Problemen nur Exponentialzeitalgorithmen auf deterministischen Rechenmaschinen. Andere Klassen von Problemen, welche garantiert mindestens exponentielle Laufzeit benötigen, veranschaulichen die derzeit praktische Unlösbarkeit von NP-vollständigen Problemen.

Im Gegensatz zu diesen Problemen, die oberhalb der Klasse NP liegen, ist für NP-vollständige Probleme wegen des offenen P-NP-Problems nicht bewiesen, dass ein optimaler Algorithmus exponentielle Laufzeit benötigt. Würde man für eines dieser Probleme einen auf deterministischen Rechenmaschinen polynomiell zeitbeschränkten Algorithmus finden, so könnte jedes beliebige Problem aus NP durch Polynomialzeitreduktion darauf reduziert und somit in deterministischer Polynomialzeit gelöst werden; in diesem Falle wäre also P = NP.

Da es bisher nicht gelungen ist, einen solchen Algorithmus zu entwerfen, vermutet der Großteil der Fachwelt, dass P≠NP gilt. Dies könnte mathematisch dadurch nachgewiesen werden, dass für ein Problem aus der Klasse NP bewiesen wird, dass kein deterministischer Polynomialzeitalgorithmus zu dessen Lösung existiert.

Denkbare Szenarien für eine Lösung des Problems wären

• Es wird bewiesen, dass P ≠ NP
• Es wird bewiesen, dass P ≠ NP logisch unabhängig von ZFC ist
• Es wird bewiesen, dass P = NP, und für ein NP-vollständiges Problem wird ein Algorithmus angegeben
• Es wird mittels nicht-konstruktiver Techniken bewiesen, dass P = NP gilt, jedoch ohne einen expliziten Algorithmus zu konstruieren.

Für die beiden letztgenannten Fälle ist noch anzumerken, dass explizite Algorithmen für NP-vollständige Probleme bekannt sind die im Falle P = NP nachweislich in P liegen, d.h. der letztgenannte Fall impliziert automatisch den zu vorletzt genannten Fall.

Für die Schwierigkeit des Problems spricht, dass bereits für verschiedene Beweistechniken gezeigt wurde, dass sie allein nicht ausreichend sind, um die Fragestellung zu klären.

Relativierende Beweistechniken

Ein Beweis für die Beziehung zweier Komplexitätsklassen ist relativierend, wenn die Beziehung für beliebig hinzugefügte Orakel erhalten bleibt. Unter die Klasse der relativierenden Beweistechniken fällt z. B. auch das in der Komplexitätstheorie häufig eingesetzte Verfahren der Diagonalisierung. Zeigt man beispielsweise $K \neq K'$ mittels Diagonalisierung, so gilt automatisch $K^A \neq K'^A$ für jedes Orakel A. Der folgende wichtige Satz von Theodore Baker, John Gill und Robert Solovay^[2] beweist, dass relativierende Beweistechniken kein probates Mittel für das P-NP-Problem sein können und viele Angriffsmethoden auf das P-NP-Problem aus der theoretischen Informatik hierdurch ausfallen:

Es existieren zwei Orakel A und B, so dass $\operatorname{P}^A = \operatorname{NP}^A$ und $\operatorname{P}^B \neq \operatorname{NP}^B$.

Natürliche Beweise

Alexander Alexandrowitsch Rasborow und Steven Rudich führten das Konzept der „Natürlichen Beweise“ (Natural Proofs) in ihrer gleichnamigen Arbeit von 1994 ein. Unter der allgemeinen vermuteten Annahme, dass bestimmte Einwegfunktionen existieren, zeigten sie, dass es nicht möglich ist, P und NP durch eine bestimmte Sorte kombinatorischer Beweistechniken zu trennen.

Vereinfacht formuliert ist ein Beweis „natürlich“, wenn er ein Kriterium für „Einfachheit“ definiert und zeigt, dass Funktionen aus P diese Eigenschaft haben und es ein NP-vollständiges Problem gibt, welches diese Eigenschaft nicht besitzt. Das Kriterium für „Einfachheit“ muss hier zum einen für ausreichend große Menge von Funktionen gelten, zum anderen ausreichend einfach nachprüfbar sein.

Beweisversuche

Am 6. August 2010 schickte der bei Hewlett-Packard angestellte Mathematiker Vinay Deolalikar einen möglichen Beweis für P ≠ NP an verschiedene Forscher.^[3] Zwei Tage später tauchte die Vorabversion des Beweises im Web auf. Nach einigen Tagen behauptete Neil Immerman, zwei fatale Fehler in dem Beweis gefunden zu haben.^[4]

Praktische Relevanz

Sehr viele auch praktisch relevante Probleme sind NP-vollständig. Die Lösung des Problems könnte daher von großer Bedeutung sein. Der Beweis von P = NP würde bedeuten, dass für Probleme der bisherigen Klasse NP Algorithmen existieren, die eine Lösung in – wesentlich schnellerer – Polynomialzeit generieren können. Da es jedoch in den vergangenen Jahrzehnten noch nicht gelungen ist, auch nur einen einzigen derartigen Algorithmus zu finden, wird in der Fachwelt angezweifelt, dass diese Algorithmen überhaupt existieren.

Viele praktische Anwendungen für NP-vollständige Probleme, wie zum Beispiel das Problem des Handlungsreisenden, das Rucksackproblem oder das Problem der Färbung von Graphen, wären im Fall P = NP theoretisch optimal in kurzer Zeit lösbar. Allerdings könnten in einer polynomialen Lösung die Exponenten und Konstanten auch derart hoch sein, dass für praktisch relevante Anwendungen ein exponentielles Lösungverfahren immer noch das bessere ist.

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

In der Kryptologie ist Komplexität im Gegensatz zu den meisten anderen Bereichen eine erwünschte Eigenschaft. Die Sicherheit von einigen asymmetrischen Verschlüsselungsverfahren basiert allein auf diesem Faktor. Ein NP-Algorithmus kann ein beliebiges asymmetrisches Kryptosystem brechen, indem er den geheimen Schlüssel „errät“ und mit dem Verfahren, das der eigentliche Empfänger der Nachricht benutzen würde, effizient entschlüsseln bzw. verifizieren.

Siehe auch

• Karps 21 NP-vollständige Probleme
• Parametrisierte Algorithmen

Einzelnachweise

1. ↑ Richard E. Ladner: On the structure of polynomial time reducibility. In: Journal of the ACM. 22, Nr. 1, 1975, S. 151–171 (doi:10.1145/321864.321877).
2. ↑ Theodore Baker, John Gill, Robert Solovay: Relativizations of the P=?NP question. In: SIAM Journal on Computing. 4, Nr. 4, 1975, S. 431–442, 1975 (doi:10.1137/0204037).
3. ↑ http://www.hpl.hp.com/personal/Vinay_Deolalikar/
4. ↑ Fatal Flaws in Deolalikar’s Proof? im Blog von Richard Jay "Dick" Lipton, Meldung vom 12. August 2010

Weblinks

• Clay Mathematics Institute: P vs NP Problem (englisch)
• Was genau ist NP? Eine Problemannäherung (deutsch)
• „The P-versus-NP page“: Eine Sammlung von Links zu wissenschaftlichen Artikeln und Lösungsversuchen zum P-NP-Problem (englisch)
• „heise online News“: News über den Forscher Vinay Deolalikar, der behauptet das Problem gelöst zu haben. Eine eingehende Prüfung seines Beweises ist jedoch noch erforderlich. (Stand: 10. August 2010)
• Lance Fortnow Status of P vs. NP, Communications of the ACM Bd.52, 2009, S.78-86