P-NP-Problem

aus Wikipedia, der freien Enzyklopädie
Zur Navigation springen Zur Suche springen

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] Eine weitere frühe Formulierung findet sich in einem Brief von John Forbes Nash 1950 an die National Security Agency, wobei es um Kryptographie ging.[5]

P und NP[Bearbeiten | Quelltext 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.[6]

Die Komplexitätstheorie klassifiziert Probleme, die von Computern berechnet werden können, anhand des zu ihrer Lösung erforderlichen Aufwands. Ein Problem ist dabei immer eine Schablone, aus der sich unendlich viele Probleminstanzen ergeben. Ein Problem ist beispielsweise, zu entscheiden, ob eine Natürliche Zahl prim ist, und eine Instanz des Problems wäre dann eine bestimmte natürliche Zahl. Man untersucht nun, wie schnell der Berechnungsaufwand für das Lösen einer Instanz mit deren Größe wächst. Als Maß für die Größe dient in der Regel die Länge (Zeichenzahl) der Eingabe, mit der die Instanz dem Lösungsalgorithmus eingegeben wird.

Das hier genutzte Maß für den Berechnungsaufwand ist die Zahl der Rechenschritte, die der Algorithmus für eine Probleminstanz benötigt (Zeitkomplexität). Zu deren genauer Analyse werden außerdem formale Maschinenmodelle benötigt, um die Lösungsalgorithmen darzustellen. Ein häufig verwendetes Modell ist dabei die deterministische Turingmaschine, die als die Abstraktion eines realen Computers angesehen werden kann.

P[Bearbeiten | Quelltext bearbeiten]

Eine der Problemkategorien ist die Komplexitätsklasse . Sie enthält die Probleme, zu denen eine deterministische Turingmaschine existiert, die das Problem in Polynomialzeit löst. Das heißt, es existiert eine Funktion mit , die die Laufzeit der Turingmaschine nach oben beschränkt: sie braucht für keine Probleminstanz (mit Länge ) mehr als Rechenschritte. Probleme aus sind somit deterministisch in Polynomialzeit lösbar.

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

NP[Bearbeiten | Quelltext bearbeiten]

Ein weiteres wichtiges Modell ist die nichtdeterministische Turingmaschine, die eine Verallgemeinerung 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 damit eine weitere Komplexitätsklasse definiert werden kann, die viele Probleme von praktischem Interesse enthält, von denen man noch nicht weiß, ob sie in liegen.

ist definiert als die Menge aller von nichtdeterministischen Turingmaschinen in Polynomialzeit lösbaren Probleme. Da die Probleme aus auch mit einer nichtdeterministischen Maschine in Polynomialzeit lösbar sind, ist eine Teilmenge von .

Man kann gleichbedeutend definieren als die Menge der Probleme, von denen sich in Polynomialzeit mit einer deterministischen Turingmaschine entscheiden lässt, ob eine vorgeschlagene Lösung zutrifft.

Ist P=NP?[Bearbeiten | Quelltext bearbeiten]

Unbekannt ist, ob die beiden Klassen und identisch sind, ob also auch die schwersten Probleme der Klasse mit deterministischen Maschinen effizient lösbar sind. Um den Begriff des „schwersten Problems in “ formal zu fassen, wurde der Begriff der NP-Schwere eingeführt. Ein Problem X ist NP-schwer, wenn man jedes Problem in durch Polynomialzeitreduktion auf X reduzieren kann. Aus der deterministischen Lösbarkeit von X in Polynomialzeit würde dann folgen, dass auch jedes Problem in deterministisch in polynomialer Zeit lösbar ist. Ein Problem, das in liegt und NP-schwer ist, heißt NP-vollständig.

Ein anschauliches NP-vollständiges Problem ist das Rucksackproblem: Ein Behälter einer bestimmten Größe soll so mit einer Auswahl aus vorgegebenen Gegenständen gefüllt werden, dass der Inhalt so wertvoll wie nur möglich ist, ohne die Kapazität des Behälters zu überschreiten. Ein anderes wichtiges Beispiel ist das Erfüllbarkeitsproblem der Aussagenlogik.

Es wurde außerdem gezeigt: wenn ist und somit die NP-vollständigen Probleme nicht in liegen, dann gibt es in Probleme, die weder NP-vollständig noch in sind, die also in ihrer Schwierigkeit eine Zwischenstufe darstellen. Ein Kandidat für ein solches Problem ist das Graphen-Isomorphismus-Problem, von dem man bisher weder weiß, ob es in liegt, noch ob es NP-vollständig ist.

Lösung des Problems[Bearbeiten | Quelltext bearbeiten]

Bisher sind zum exakten Lösen von NP-vollständigen Problemen nur Exponentialzeitalgorithmen auf deterministischen Rechenmaschinen bekannt. Andere Klassen von Problemen, die garantiert mindestens exponentielle Laufzeit benötigen (EXPTIME-vollständige Probleme), veranschaulichen die derzeit praktische Unlösbarkeit von NP-vollständigen Problemen.

Im Gegensatz zu diesen Problemen, die oberhalb der Klasse 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 durch Polynomialzeitreduktion darauf reduziert und somit in deterministischer Polynomialzeit gelöst werden; in diesem Falle wäre also .

Da es bisher nicht gelang, einen solchen Algorithmus zu entwerfen, vermutet der Großteil der Fachwelt, dass gilt. Dies könnte mathematisch dadurch nachgewiesen werden, dass für ein Problem aus der Klasse 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 .
  • Es wird bewiesen, dass logisch unabhängig von ZFC ist.
  • Es wird bewiesen, dass , indem für ein NP-vollständiges Problem ein effizienter Algorithmus angegeben wird.
  • Es wird mittels nicht-konstruktiver Techniken bewiesen, dass gilt, also ohne einen expliziten Algorithmus zu konstruieren.[7]

Für die Komplexität 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 | Quelltext 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 mittels Diagonalisierung, so gilt automatisch für jedes Orakel . Der folgende wichtige Satz von Theodore Baker, John Gill und Robert Solovay[8] 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 und , so dass und .

Natürliche Beweise[Bearbeiten | Quelltext 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, und 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 diese Eigenschaft haben und es ein NP-vollständiges Problem gibt, das 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 | Quelltext bearbeiten]

Es wurden verschiedene Beweistechniken entwickelt.[9] In jüngerer Zeit bekanntgeworden ist der Beweisversuch für vom 6. August 2010 des bei Hewlett-Packard angestellten Mathematikers Vinay Deolalikar.[10] Er galt schnell als widerlegt, aber es gebührt ihm das Verdienst, sowohl in der Öffentlichkeit als auch in Fachkreisen das Thema zeitweise neu in den Fokus gerückt zu haben.[11]

Praktische Relevanz[Bearbeiten | Quelltext 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 würde bedeuten, dass für Probleme der bisherigen Klasse 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 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 wären NP-Probleme endgültig als schwer lösbar klassifiziert. entspricht derzeit der Annahme der meisten Wissenschaftler, und der Beweis wäre weniger folgenschwer als der Beweis von .

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 | Quelltext bearbeiten]

Literatur[Bearbeiten | Quelltext bearbeiten]

  • Scott Aaronson: , in: John Forbes Nash, Michael Rassias (Hrsg.), Open problems mathematics, Springer 2016, S. 1–122[12]
  • Stephen A. Cook: vs. problem, Clay Mathematics Institute (Millennium Problems)
  • Lance Fortnow: Status of the problem, Comm. ACM, Band 52, 2009, S. 78–86, Online
  • Lance Fortnow: The golden ticket. and the search for the impossible, Princeton University Press 2013
  • Richard J. Lipton: The Question and Gödel's Lost Letter, Springer 2010

Einzelnachweise[Bearbeiten | Quelltext 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. Scott Aaronson, P =? NP, in: Nash, Rassias, Open problems in Mathematics, Springer 2016, S. 1 (mit Zitat aus dem Brief)
  6. 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).
  7. Diese Variante wird von Donald Knuth für zutreffend gehalten, siehe die Argumentation und Interpretation in Twenty Questions for Donald Knuth, Mai 2014, Frage 17.
  8. 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).
  9. The Status of the P Versus NP Problem
  10. Newsticker Heise 2010
  11. Alexander Nazaryan: A Most Profound Math Problem. In: The New Yorker. 2. Mai 2013. Abgerufen im 15. Februar 2017.
  12. Sein Blog dazu mit dem Artikel in überarbeiteter Fassung.

Weblinks[Bearbeiten | Quelltext bearbeiten]

  • „The P-versus-NP page“: Eine Sammlung von Links zu wissenschaftlichen Artikeln und Lösungsversuchen zum P-NP-Problem von Gerhard Woeginger (englisch)