P-NP-Problem

Das P-NP-Problem (auch P≟NP, P versus NP) ist ein ungelöstes Problem der Komplexitätstheorie in der theoretischen Informatik. Dabei geht es um die Frage, ob die Menge der Probleme, die schnell lösbar sind (${\displaystyle P}$), und die Menge der Probleme, bei denen man eine vorgeschlagene Lösung schnell auf Korrektheit überprüfen kann (${\displaystyle NP}$), identisch sind. Schnell lösbar bzw. prüfbar bedeutet hier, dass dafür ein Algorithmus existiert, dessen Rechenaufwand (Zahl der Rechenschritte), abhängig von der Größe der Eingabe, durch eine Polynomfunktion beschränkt ist. Die Größe der Eingabe ist hier vereinfacht gesagt die Anzahl der Elemente, die dem Algorithmus eingegeben werden. Beim Sortieren von Karteikarten wäre dies zum Beispiel die Anzahl der Karteikarten.

Es ist zwar klar, dass man bei allen schnell lösbaren Problemen auch schnell die Korrektheit einer Lösung überprüfen kann, in der umgekehrten Richtung ist dies jedoch nicht klar: Für manche Probleme existiert zwar ein Algorithmus, der eine vorgeschlagene Lösung schnell überprüfen kann, aber es konnte weder ein Algorithmus gefunden werden, der auch schnell eine korrekte Lösung findet, noch konnte die Unmöglichkeit eines solchen Algorithmus bewiesen werden. Somit ist die Fragestellung ungelöst. Würde man für alle schnell prüfbaren Probleme ${\displaystyle NP}$ einen Algorithmus finden, der diese auch schnell löst, so gälte ${\displaystyle P=NP}$. Könnte für mindestens ein Problem aus ${\displaystyle NP}$ gezeigt werden, dass dieses prinzipiell nicht schnell lösbar ist, wäre ${\displaystyle P\neq NP}$ bewiesen.

Geschichte

Erkannt wurde das P-NP-Problem zu Beginn der 1970er Jahre durch unabhängige Arbeiten von Stephen Cook und Leonid Levin. Es 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 NP

(c) Booyabazooka, CC BY-SA 3.0

Die Komplexitätstheorie klassifiziert Probleme, die von Computern berechnet werden können, anhand des zu ihrer Lösung erforderlichen Aufwands von Zeit oder Speicher, genauer: danach, wie schnell der Aufwand mit der Größe des Problems wächst. Ein Problem ist beispielsweise das Sortieren von Karteikarten. Dabei kann untersucht werden, wie sich die benötigte Zeit ändert, wenn z. B. ein doppelt so hoher Stapel sortiert wird.

Das hier genutzte Maß für den Berechnungsaufwand ist die Zahl der Rechenschritte, die der Algorithmus für ein Problem benötigt (Zeitkomplexität). Um den Berechnungsaufwand eindeutig anzugeben, werden außerdem formale Maschinenmodelle zur Darstellung der Lösungsalgorithmen benötigt. Ein häufig verwendetes Modell ist dabei die deterministische Turingmaschine, die als die Abstraktion eines realen Computers angesehen werden kann.

P

Eine der Problemkategorien ist die Komplexitätsklasse ${\displaystyle P}$. Sie enthält die Probleme, für die eine deterministische Turingmaschine existiert, die das Problem in Polynomialzeit löst. Das heißt, es gibt ein Polynom ${\displaystyle f(n)=n^{k}+c}$ mit ${\displaystyle c,k\in \mathbb {N} }$, so dass die Turingmaschine für jede beliebige Probleminstanz ${\displaystyle x}$ höchstens ${\displaystyle f(\operatorname {len} (x))}$ Rechenschritte braucht, wobei ${\displaystyle \operatorname {len} (x)}$ die Länge der Eingabe ist, mit der die Probleminstanz der Maschine eingegeben wird. Probleme aus ${\displaystyle P}$ sind somit deterministisch in Polynomialzeit lösbar.

Das oben erwähnte Sortierproblem ist in P, weil es Algorithmen gibt, die eine Zahl ${\displaystyle n}$ von Datensätzen (Karteikarten) in einer Zeit sortierten, die durch eine quadratische Funktion in ${\displaystyle n}$ beschränkt ist. Ein weiteres Beispiel eines Problems in ${\displaystyle P}$ ist das Schaltkreis-Auswertungsproblem.

Der Unterschied zwischen einer Turingmaschine und realen Computern spielt hier keine Rolle, weil jeder Algorithmus, der auf einem realen Rechner ein Problem in Polynomialzeit löst, auch mit einer Turingmaschine in polynomieller Zeit realisiert werden kann (wobei aber der Grad des die Laufzeit beschränkenden Polynoms in der Regel höher sein wird).

NP

Ein weiteres Maschinenmodell ist die nichtdeterministische Turingmaschine (NTM), sie ist eine Verallgemeinerung der deterministischen Variante. Eine NTM kann in einer Situation mehrere Möglichkeiten haben, ihre Berechnung fortzusetzen, der Rechenweg ist also nicht immer eindeutig bestimmt. Es handelt sich dabei um ein theoretisches Modell, es gibt keine real existierenden Computer, die ihren Rechenweg derart verzweigen können. Sein Nutzen ist in diesem Zusammenhang, dass damit eine weitere Komplexitätsklasse ${\displaystyle NP}$ definiert werden kann, die viele Probleme von praktischem Interesse enthält, von denen man noch nicht weiß, ob sie in ${\displaystyle P}$ liegen.

${\displaystyle NP}$ ist definiert als die Menge der von einer NTM in Polynomialzeit lösbaren Probleme. Die deterministische Turingmaschine ist ein Spezialfall der NTM, sie verzichtet auf das Verzweigen des Rechenwegs. Darum ist ${\displaystyle P}$ eine Teilmenge von ${\displaystyle NP}$.

Man kann ${\displaystyle NP}$ 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. Beispielsweise ist derzeit kein deterministischer Algorithmus bekannt, um eine gegebene Zahl in Polynomialzeit zu faktorisieren. Es ist jedoch sehr einfach prüfbar, ob ein vorgeschlagener Faktor die Zahl ohne Rest teilt und damit tatsächlich ein Faktor der Zahl ist.

Ist P=NP?

(c) Behnam Esfahbod, CC BY-SA 3.0

Unbekannt ist, ob die beiden Klassen ${\displaystyle P}$ und ${\displaystyle NP}$ identisch sind, ob also auch die schwersten Probleme der Klasse ${\displaystyle NP}$ mit deterministischen Maschinen effizient lösbar sind. Um den Begriff des „schwersten Problems in ${\displaystyle NP}$“ formal zu fassen, wurden die Begriffe der NP-Vollständigkeit und der NP-Schwere eingeführt. Ein Problem X ist NP-schwer, wenn man jedes Problem in ${\displaystyle NP}$ durch Polynomialzeitreduktion auf X reduzieren kann. Sollte man ein NP-schweres Problem X finden, das sich deterministisch in Polynomialzeit lösen lässt, könnte man auch jedes Problem in ${\displaystyle NP}$ deterministisch-polynomiell lösen, indem man es auf X zurückführt, und es wäre ${\displaystyle P=NP}$ gezeigt. Ein Problem, das in ${\displaystyle NP}$ 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: falls ${\displaystyle P\neq NP}$ ist und somit die NP-vollständigen Probleme nicht in ${\displaystyle P}$ liegen, dann gibt es in ${\displaystyle NP}$ auch Probleme, die weder NP-vollständig noch in ${\displaystyle P}$ sind, die also in ihrer Schwierigkeit eine Zwischenstufe darstellen (Satz von Ladner).^[7] Ein Kandidat für ein solches Problem ist das Graphen-Isomorphismus-Problem, von dem man bisher weder weiß, ob es in ${\displaystyle P}$ liegt, noch ob es NP-vollständig ist.

Lösung des Problems

Bisher sind zum exakten Lösen von NP-vollständigen Problemen nur Exponentialzeitalgorithmen auf deterministischen Rechenmaschinen bekannt. Es ist aber nicht bewiesen, dass es keine polynomzeitlichen Algorithmen für die Lösung gibt, im Gegensatz zu einer anderen Klasse von Problemen, die garantiert mindestens exponentielle Laufzeit benötigen (EXPTIME-vollständige Probleme) und die somit beweisbar außerhalb der Klasse ${\displaystyle P}$ liegen. Würde man für eines dieser NP-vollständigen Probleme für alle Eingaben einen auf deterministischen Rechenmaschinen polynomiell zeitbeschränkten Algorithmus finden (Klasse ${\displaystyle P}$), so könnte jedes beliebige Problem aus ${\displaystyle NP}$ durch Polynomialzeitreduktion darauf reduziert und somit in deterministischer Polynomialzeit gelöst werden; in diesem Falle wäre also ${\displaystyle P=NP}$.

Da es bisher nicht gelang, einen solchen Algorithmus zu entwerfen, vermutet der Großteil der Fachwelt, dass ${\displaystyle P\neq NP}$ gilt. Dies könnte mathematisch dadurch nachgewiesen werden, dass für ein Problem aus der Klasse ${\displaystyle 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 ${\displaystyle P\neq NP}$.
• Es wird bewiesen, dass ${\displaystyle P\neq NP}$ logisch unabhängig von ZFC ist.
• Es wird bewiesen, dass ${\displaystyle P=NP}$, indem für ein NP-vollständiges Problem ein effizienter Algorithmus angegeben wird.
• Es wird mittels nicht-konstruktiver Techniken bewiesen, dass ${\displaystyle P=NP}$ 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 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 ${\displaystyle K\neq K'}$ mittels Diagonalisierung, so gilt automatisch ${\displaystyle K^{A}\neq K'^{A}}$ für jedes Orakel ${\displaystyle A}$. 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 ${\displaystyle A}$ und ${\displaystyle B}$, so dass ${\displaystyle \operatorname {P} ^{A}=\operatorname {NP} ^{A}}$ und ${\displaystyle \operatorname {P} ^{B}\neq \operatorname {NP} ^{B}}$.

Natürliche Beweise

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, ${\displaystyle P}$ und ${\displaystyle 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 ${\displaystyle P}$ 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 eine ausreichend große Menge von Funktionen gelten, zum anderen ausreichend einfach nachprüfbar sein.

Beweisversuche

Viele Amateure und professionelle Forscher haben sich am P-NP-Problem versucht und ihre Resultate veröffentlicht. Gerhard Woeginger betrieb eine Sammlung an Beweisversuchen. Im September 2016 enthielt sie 62 angebliche Beweise für ${\displaystyle P=NP}$, 50 Beweise, die ${\displaystyle P\neq NP}$ zeigen sollten, zwei Beweise, dass das Problem nicht beweisbar ist, und einen Beweis, dass es unentscheidbar ist.^[10] Unter all diesen Arbeiten gibt es nur eine einzige, die in einer peer-reviewed Zeitschrift erschienen ist, von den Experten auf diesem Gebiet gründlich überprüft wurde und von der Forschungsgemeinschaft allgemein als korrekt akzeptiert wird, nämlich die Arbeit von Mihalis Yannakakis, die allerdings nicht die P-gegen-NP-Frage klärt, sondern nur zeigt, dass ein bestimmter Ansatz zur Klärung dieser Frage niemals funktionieren wird.

In jüngerer Zeit bekanntgeworden ist der Beweisversuch für ${\displaystyle P\neq NP}$ vom 6. August 2010 des bei Hewlett-Packard angestellten Mathematikers Vinay Deolalikar.^[11] Er galt schnell als widerlegt, aber es gebührt ihm der Verdienst, sowohl in der Öffentlichkeit als auch in Fachkreisen das Thema zeitweise neu in den Fokus gerückt zu haben.^[12]

Praktische Relevanz

Sehr viele praktisch relevante Probleme sind NP-vollständig. Die Lösung des P-NP-Problems könnte daher von großer Bedeutung sein. Der Beweis von ${\displaystyle P=NP}$ würde bedeuten, dass für die Probleme der Klasse ${\displaystyle NP}$ Algorithmen existieren, die sie in Polynomialzeit lösen. Da jedoch in den vergangenen Jahrzehnten trotz intensiver Suche kein Algorithmus gefunden wurde, der ein NP-vollständiges Problem in Polynomialzeit löst, wird in der Fachwelt angezweifelt, dass solche Algorithmen überhaupt existieren, d. h., man geht von ${\displaystyle P\neq NP}$ aus.

Viele 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 ${\displaystyle P=NP}$ theoretisch optimal in kurzer Zeit lösbar. Allerdings könnten die Exponenten und Konstanten der Laufzeitfunktion eines polynomialen Verfahrens auch derart hoch sein, dass für praktisch relevante Anwendungen eines der bisher bekannten Lösungsverfahren, z. B. ein approximatives oder probabilistisches, immer noch das bessere ist.

Mit dem Beweis von ${\displaystyle P\neq NP}$ wären NP-Probleme endgültig als schwer lösbar klassifiziert. ${\displaystyle P\neq NP}$ entspricht derzeit der Annahme der meisten Wissenschaftler, und der Beweis wäre weniger folgenschwer als der Beweis von ${\displaystyle 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, dieses effizient entschlüsselt und so den Schlüssel verifiziert. Ein Beweis von ${\displaystyle P=NP}$ würde also bedeuten, dass die Aussicht besteht, diese Kryptosysteme in der Praxis zu brechen. Entsprechend steht die Lösung des P-NP-Problems in Zusammenhang mit der offenen Frage, ob es Einwegfunktionen gibt. Falls es sie gibt, würde ${\displaystyle P\neq NP}$ folgen.

Siehe auch

• Parametrisierter Algorithmus
• Karps 21 NP-vollständige Probleme

Literatur

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

Einzelnachweise

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. ↑ Gerhard Woeginger: P-versus-NP page. 26. September 2016, abgerufen am 3. April 2020 (englisch). 
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.

Weblinks

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