Hauptmenü öffnen

P-NP-Problem

ungelöstes Problem der Mathematik und theoretischen Informatik

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 an 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 1955 an die National Security Agency, wobei es um Kryptographie ging.[5][6]

P und NPBearbeiten

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

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.

PBearbeiten

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.

NPBearbeiten

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 möglicherweise 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

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 ProblemsBearbeiten

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

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 BeweistechnikenBearbeiten

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[9] 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 BeweiseBearbeiten

Alexander Alexandrowitsch Rasborow und Steven Rudich führten das Konzept der „Natürlichen Beweise“ (engl. 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.

BeweisversucheBearbeiten

Es wurden verschiedene Beweistechniken entwickelt.[10] In jüngerer Zeit bekanntgeworden ist der Beweisversuch für   vom 6. August 2010 des bei Hewlett-Packard angestellten Mathematikers Vinay Deolalikar.[11] 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.[12]

Praktische RelevanzBearbeiten

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 auchBearbeiten

LiteraturBearbeiten

  • Scott Aaronson:  , in: John Forbes Nash, Michael Rassias (Hrsg.), Open problems mathematics, Springer 2016, S. 1–122[13]
  • 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

EinzelnachweiseBearbeiten

  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. National Cryptologic Museum Opens New Exhibit on Dr. John Nash, NSA 2012. Die Stelle auf S. 4 des Briefs von 1955 lautet: Now my general conjecture is as follows: for almost all sufficiently complex types of enciphering, especially where the instructions given by different portions of the key interact complexly with each other in the determination of their ultimate effects on the enciphering, the mean key computation length increases exponentially with the length of the key, or in other words, the information content of the key. The significance of this general conjecture, assuming its truth, is easy to see. It means that it is quite feasible to design ciphers that are effectively unbreakable. .... The nature of this conjecture is such that I cannot prove it, even for a special type of ciphers. Nor do I expect it to be proven.
  7. 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).
  8. 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.
  9. 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).
  10. The Status of the P Versus NP Problem
  11. Newsticker Heise 2010
  12. Alexander Nazaryan: A Most Profound Math Problem. In: The New Yorker. 2. Mai 2013. Abgerufen am 15. Februar 2017.
  13. Sein Blog dazu mit dem Artikel in überarbeiteter Fassung.

WeblinksBearbeiten

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