P-NP-Problem

aus Wikipedia, der freien Enzyklopädie
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] 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. 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 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, 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 (mit einem Algorithmus, einer „Programmierung“) 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 Eingabe (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 durch nichtdeterministische Turingmaschinen eine weitere Komplexitätsklasse unterschieden werden kann, die ihrerseits einschließt.

Die Komplexitätsklasse ist die Menge aller von nichtdeterministischen Turingmaschinen in Polynomialzeit lösbaren Probleme. Diese Menge enthält eine sehr große Zahl relevanter Problemstellungen. Da sich die Probleme aus natürlich auch nichtdeterministisch in Polynomialzeit lösen lassen, ist eine Teilmenge von . Eine alternative Definition von ist, dass 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, 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.

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

Siehe auch[Bearbeiten | Quelltext bearbeiten]

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. 2. Mai 2013. Abgerufen am 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)