P-NP-Problem

aus Wikipedia, der freien Enzyklopädie
(Weitergeleitet von P/NP-Problem)
Wechseln zu: Navigation, Suche

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 sich die Frage, in welcher Beziehung die beiden Komplexitätsklassen P und NP zueinander 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.

Wie später bekannt wurde, findet sich schon eine Formulierung des Problems in einem Brief von Kurt Gödel, den dieser John von Neumann kurz vor dessen Tod schickte (am 20. März 1956).[1][2][3][4]

P und NP[Bearbeiten]

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.[5]

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; sie wird hierbei immer im Verhältnis zur Länge der Eingabe (im nachfolgenden n genannt) 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.

P[Bearbeiten]

Eine der komplexitätstheoretischen Problemkategorien ist die Komplexitätsklasse P. Zu jedem Problem dieser Klasse existiert eine deterministische Turingmaschine (mit einem Algorithmus, einer „Programmierung“), welche das Problem löst und zu der ein Polynom der Form n^k (wobei k eine Konstante ist) angegeben werden kann, welches die Zeitkomplexität des Lösens 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.

EXP[Bearbeiten]

Eine weitere anhand der deterministischen Turingmaschine definierte Problemmenge ist die Komplexitätsklasse EXP. Anstelle eines Polynoms kann hier als obere Schranke für die Zeitkomplexität nur eine Funktion der Form 2^n in Abhängigkeit von der Eingabelänge n angegeben werden. Die Lösung der schwersten Probleme dieser Klasse benötigt also exponentielle Zeit. Weiterhin ist die Klasse P vollständig in EXP enthalten: Jedes Problem, das mit polynomialem Zeitbedarf gelöst werden kann, bleibt (für große n) auch unterhalb eines exponentiellen Zeitbedarfs.

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^n 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.

Das heißt, es gibt Probleme in EXP, deren Lösungszeitbedarf eine exponentielle obere Schranke besitzen, aber garantiert durch keine polynomielle Schranke beschrieben werden kann.

NP[Bearbeiten]

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.

Ist P=NP?[Bearbeiten]

Unklar ist, ob die beiden Klassen P und NP 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. Um den Begriff des „schwersten Problems in NP“ formal zu fassen, wurde der Begriff der NP-Schwere eingeführt. Ein Problem ist NP-schwer, wenn seine Lösung (in Polynomialzeit) die Lösung jedes anderen Problems in NP in polynomialer Zeit ermöglichen würde (unter Verwendung einer deterministischen Maschine; Polynomialzeitreduktion). Ein Problem, das in NP liegt und NP-schwer ist, heißt NP-vollständig.

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 Inhalt so wertvoll wie nur möglich ist. Ein anderes wichtiges Beispiel ist das Erfüllbarkeitsproblem der Aussagenlogik.

Lösung des Problems[Bearbeiten]

Bisher sind zum exakten Lösen von NP-vollständigen Problemen nur Exponentialzeitalgorithmen auf deterministischen Rechenmaschinen bekannt. 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 gelang, 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, indem für ein NP-vollständiges Problem ein effizienter Algorithmus angegeben wird.
  • Es wird mittels nicht-konstruktiver Techniken bewiesen, dass P = NP gilt, also ohne einen expliziten Algorithmus zu konstruieren.

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[Bearbeiten]

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[6] 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[Bearbeiten]

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[Bearbeiten]

Am 6. August 2010 schickte der bei Hewlett-Packard angestellte Mathematiker Vinay Deolalikar einen möglichen Beweis für P ≠ NP an verschiedene Forscher.[7] 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.[8] Der Beweisversuch wurde wegen seines interessanten Ansatzes unter Komplexitätstheoretikern viel diskutiert.[9]

Praktische Relevanz[Bearbeiten]

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ösungsverfahren 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 einiger asymmetrischer 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[Bearbeiten]

Einzelnachweise[Bearbeiten]

  1. John Dawson Kurt Gödel - Leben und Werk, Springer Verlag 1997, S. 177, dort wird der Brief zitiert
  2. Janis Hartmanis Gödel, von Neumann and the P?=NP Problem, Bulletin European Assoc. Theor. Computer Science, 38, 1989, S. 101-107
  3. The Gödel Letter, Blog von Lipton, mit englischer Übersetzung
  4. Michael Sipser The history and the status of the P versus NP Question, 24. STOC Proc., 1992, S. 603-618
  5. 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).
  6. 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).
  7. http://www.hpl.hp.com/personal/Vinay_Deolalikar/
  8. Fatal Flaws in Deolalikar’s Proof? im Blog von Richard Jay "Dick" Lipton, Meldung vom 12. August 2010
  9. Kenneth L. Clarkson, Ronald Fagin, Ryan Williams: P v. NP Discussion at IBM Almaden Research Center. Abgerufen am 3. Februar 2012 (flash video (45 min.), englisch).

Weblinks[Bearbeiten]