P-NP-Problem

Ungelöstes Problem in der Informatik:

Wenn die Lösung eines Problems leicht auf Korrektheit zu überprüfen ist, muss das Problem dann auch leicht zu lösen sein?

(weitere ungelöste Probleme in der Informatik) ⓘ

Das P-versus-NP-Problem ist ein großes ungelöstes Problem in der theoretischen Informatik. Informell ausgedrückt, geht es um die Frage, ob jedes Problem, dessen Lösung schnell verifiziert werden kann, auch schnell gelöst werden kann. ⓘ

Der oben verwendete informelle Begriff "schnell" bedeutet, dass es einen Algorithmus gibt, der die Aufgabe in polynomialer Zeit löst, so dass die Zeit zur Lösung der Aufgabe als polynomiale Funktion der Größe der Eingabe für den Algorithmus variiert (im Gegensatz zu beispielsweise exponentieller Zeit). Die allgemeine Klasse von Fragen, für die ein Algorithmus eine Antwort in polynomialer Zeit liefern kann, ist "P" oder "Klasse P". Für einige Fragen gibt es keinen bekannten Weg, eine Antwort schnell zu finden, aber wenn man Informationen erhält, die zeigen, wie die Antwort lautet, ist es möglich, die Antwort schnell zu überprüfen. Die Klasse der Fragen, für die eine Antwort in polynomieller Zeit verifiziert werden kann, ist NP, was für "nondeterministische polynomielle Zeit" steht. ⓘ

Eine Antwort auf die Frage P versus NP würde bestimmen, ob Probleme, die in polynomieller Zeit verifiziert werden können, auch in polynomieller Zeit gelöst werden können. Sollte sich herausstellen, dass P ≠ NP ist, was weithin angenommen wird, würde dies bedeuten, dass es Probleme in NP gibt, die schwieriger zu berechnen als zu verifizieren sind: Sie können nicht in Polynomialzeit gelöst werden, aber die Antwort kann in Polynomialzeit verifiziert werden. ⓘ

Das Problem wurde als das wichtigste offene Problem in der Informatik bezeichnet. Abgesehen davon, dass es sich um ein wichtiges Problem der Rechentheorie handelt, hätte ein Beweis in beide Richtungen tiefgreifende Auswirkungen auf die Mathematik, die Kryptographie, die Algorithmenforschung, die künstliche Intelligenz, die Spieltheorie, die Multimediaverarbeitung, die Philosophie, die Wirtschaft und viele andere Bereiche. ⓘ

Es ist eines der sieben Millennium-Preis-Probleme, die vom Clay Mathematics Institute ausgewählt wurden und für deren erste richtige Lösung jeweils ein Preisgeld von 1.000.000 US-Dollar ausgesetzt ist. ⓘ

Beispiel

Nehmen wir Sudoku, ein Spiel, bei dem der Spieler ein teilweise ausgefülltes Zahlengitter erhält und versucht, das Gitter nach bestimmten Regeln zu vervollständigen. Gibt es bei einem unvollständigen Sudoku-Gitter beliebiger Größe mindestens eine richtige Lösung? Jede vorgeschlagene Lösung lässt sich leicht überprüfen, und die Zeit zur Überprüfung einer Lösung wächst langsam (polynomiell), wenn das Gitter größer wird. Alle bekannten Algorithmen zum Auffinden von Lösungen benötigen jedoch für schwierige Beispiele Zeit, die mit zunehmender Größe des Gitters exponentiell ansteigt. Sudoku ist also in NP (schnell überprüfbar), scheint aber nicht in P (schnell lösbar) zu sein. Tausende anderer Probleme scheinen ähnlich zu sein, da sie schnell zu prüfen, aber langsam zu lösen sind. Forscher haben gezeigt, dass viele der NP-Probleme die zusätzliche Eigenschaft haben, dass eine schnelle Lösung für ein beliebiges NP-Problem verwendet werden kann, um eine schnelle Lösung für ein beliebiges anderes NP-Problem zu finden, eine Eigenschaft, die NP-Vollständigkeit genannt wird. Jahrzehntelange Suche hat für keines dieser Probleme eine schnelle Lösung erbracht, so dass die meisten Wissenschaftler vermuten, dass keines dieser Probleme schnell gelöst werden kann. Dies konnte jedoch nie bewiesen werden. ⓘ

Geschichte

Die genaue Formulierung des P-gegen-NP-Problems wurde 1971 von Stephen Cook in seinem bahnbrechenden Aufsatz "The complexity of theorem proving procedures" (und unabhängig davon von Leonid Levin 1973) eingeführt. ⓘ

Obwohl das P-gegen-NP-Problem erst 1971 formell definiert wurde, gab es bereits vorher Andeutungen über die damit verbundenen Probleme, die Schwierigkeit des Beweises und die möglichen Konsequenzen. Im Jahr 1955 schrieb der Mathematiker John Nash einen Brief an die NSA, in dem er spekulierte, dass das Knacken eines hinreichend komplexen Codes eine Zeit erfordern würde, die exponentiell zur Länge des Schlüssels ist. Sollte dies bewiesen werden (und Nash war entsprechend skeptisch), würde dies bedeuten, was heute als P ≠ NP bezeichnet wird, da ein vorgeschlagener Schlüssel leicht in polynomieller Zeit überprüft werden kann. Ein weiterer Hinweis auf das zugrundeliegende Problem findet sich in einem Brief von Kurt Gödel an John von Neumann aus dem Jahr 1956. Gödel fragte, ob das Beweisen von Theoremen (das heute als Co-NP-komplett bekannt ist) in quadratischer oder linearer Zeit gelöst werden kann, und wies auf eine der wichtigsten Konsequenzen hin: Wenn dies der Fall ist, könnte die Entdeckung mathematischer Beweise automatisiert werden. ⓘ

Kontext

Die Beziehung zwischen den Komplexitätsklassen P und NP wird in der Theorie der rechnerischen Komplexität untersucht, dem Teil der Rechentheorie, der sich mit den Ressourcen befasst, die während der Berechnung zur Lösung eines bestimmten Problems benötigt werden. Die gebräuchlichsten Ressourcen sind Zeit (wie viele Schritte zur Lösung eines Problems erforderlich sind) und Raum (wie viel Speicherplatz zur Lösung eines Problems benötigt wird). ⓘ

Für eine solche Analyse wird ein Modell des Computers benötigt, für den die Zeit analysiert werden muss. Bei solchen Modellen wird in der Regel davon ausgegangen, dass der Computer deterministisch ist (bei gegebenem Zustand des Computers und beliebigen Eingaben gibt es nur eine mögliche Aktion, die der Computer ausführen kann) und sequentiell (er führt eine Aktion nach der anderen aus). ⓘ

In dieser Theorie besteht die Klasse P aus all jenen Entscheidungsproblemen (wie unten definiert), die auf einer deterministischen sequentiellen Maschine in einer Zeit gelöst werden können, die polynomial zur Größe der Eingabe ist; die Klasse NP besteht aus all jenen Entscheidungsproblemen, deren positive Lösungen in polynomialer Zeit verifiziert werden können, wenn die richtigen Informationen gegeben sind, oder äquivalent, deren Lösung in polynomialer Zeit auf einer nicht-deterministischen Maschine gefunden werden kann. Offensichtlich ist P ⊆ NP. Die wohl größte offene Frage in der theoretischen Informatik betrifft die Beziehung zwischen diesen beiden Klassen:

Ist P gleich NP? ⓘ

Seit 2002 hat William Gasarch drei Umfragen unter Forschern zu dieser und verwandten Fragen durchgeführt. Die Zuversicht, dass P ≠ NP ist, hat zugenommen - 2019 glaubten 88 %, dass P ≠ NP ist, im Gegensatz zu 83 % im Jahr 2012 und 61 % im Jahr 2002. Wenn man die Antworten auf Experten beschränkt, glauben 2019 99 % an P ≠ NP. Diese Umfragen sagen nichts darüber aus, ob P=NP wahr ist, wie Gasarch selbst feststellt: ″Dies bringt uns der Lösung von P=?NP oder der Frage, wann sie gelöst sein wird, nicht näher, sondern versucht, einen objektiven Bericht über die subjektive Meinung dieser Zeit zu liefern.″ ⓘ

NP-Vollständigkeit

Euler-Diagramm für P, NP, NP-komplette und NP-harte Problemmengen (mit Ausnahme der leeren Sprache und ihres Komplements, die zu P gehören, aber nicht NP-komplett sind) ⓘ

Um die Frage nach P = NP zu beantworten, ist das Konzept der NP-Vollständigkeit sehr nützlich. NP-vollständige Probleme sind eine Menge von Problemen, auf die jedes andere NP-Problem in polynomieller Zeit reduziert werden kann und deren Lösung immer noch in polynomieller Zeit verifiziert werden kann. Das heißt, jedes NP-Problem kann in ein beliebiges NP-komplettes Problem transformiert werden. Informell ist ein NP-komplettes Problem ein NP-Problem, das mindestens so "hart" ist wie jedes andere NP-Problem. ⓘ

NP-harte Probleme sind solche, die mindestens so hart sind wie NP-Probleme, d.h. alle NP-Probleme können (in polynomieller Zeit) auf sie reduziert werden. NP-harte Probleme müssen nicht in NP sein, d.h. sie müssen keine in polynomieller Zeit verifizierbaren Lösungen haben. ⓘ

Beispielsweise ist das Boolesche Erfüllbarkeitsproblem nach dem Cook-Levin-Theorem NP-komplett, d. h. jede Instanz eines beliebigen NP-Problems kann mechanisch in Polynomialzeit in eine Instanz des Booleschen Erfüllbarkeitsproblems transformiert werden. Das Boolesche Erfüllbarkeitsproblem ist eines von vielen solchen NP-kompletten Problemen. Wenn ein beliebiges NP-komplettes Problem in P liegt, dann folgt daraus, dass P = NP ist. Es hat sich jedoch gezeigt, dass viele wichtige Probleme NP-komplett sind, und es ist kein schneller Algorithmus für eines dieser Probleme bekannt. ⓘ

Allein aufgrund der Definition ist es nicht offensichtlich, dass es NP-komplette Probleme gibt; ein triviales und konstruiertes NP-komplettes Problem kann jedoch wie folgt formuliert werden: Gibt es bei einer Beschreibung einer Turing-Maschine M, die garantiert in polynomialer Zeit zum Stillstand kommt, eine Eingabe von polynomialer Größe, die M akzeptiert? Es ist in NP, weil es (bei gegebener Eingabe) einfach ist zu prüfen, ob M die Eingabe akzeptiert, indem man M simuliert; es ist NP-komplett, weil der Verifizierer für jede bestimmte Instanz eines NP-Problems als Polynomialzeitmaschine M kodiert werden kann, die die zu verifizierende Lösung als Eingabe annimmt. Die Frage, ob die Instanz eine Ja- oder Nein-Instanz ist, hängt dann davon ab, ob eine gültige Eingabe existiert. ⓘ

Das erste natürliche Problem, das sich als NP-vollständig erwies, war das boolesche Erfüllbarkeitsproblem, auch bekannt als SAT. Wie bereits erwähnt, handelt es sich hierbei um das Cook-Levin-Theorem; der Beweis, dass die Erfüllbarkeit NP-komplett ist, enthält technische Details über Turing-Maschinen, die sich auf die Definition von NP beziehen. Nachdem jedoch bewiesen wurde, dass dieses Problem NP-komplett ist, stellte der Beweis durch Reduktion einen einfacheren Weg dar, um zu zeigen, dass viele andere Probleme ebenfalls NP-komplett sind, einschließlich des bereits erwähnten Spiels Sudoku. In diesem Fall zeigt der Beweis, dass eine Lösung von Sudoku in polynomieller Zeit auch dazu verwendet werden kann, lateinische Quadrate in polynomieller Zeit zu vervollständigen. Dies wiederum führt zu einer Lösung für das Problem der Partitionierung von dreiteiligen Graphen in Dreiecke, die dann verwendet werden kann, um Lösungen für den Spezialfall von SAT, bekannt als 3-SAT, zu finden, was wiederum eine Lösung für die allgemeine boolesche Erfüllbarkeit liefert. Eine Polynomialzeitlösung für Sudoku führt also durch eine Reihe mechanischer Transformationen zu einer Polynomialzeitlösung der Erfüllbarkeit, die wiederum zur Lösung jedes anderen NP-Problems in Polynomialzeit verwendet werden kann. Durch solche Umformungen lässt sich eine große Klasse scheinbar nicht zusammenhängender Probleme aufeinander zurückführen und ist in gewissem Sinne "dasselbe Problem". ⓘ

Schwierigere Probleme

Obwohl nicht bekannt ist, ob P = NP ist, sind Probleme außerhalb von P bekannt. So wie die Klasse P durch die polynomielle Laufzeit definiert ist, ist die Klasse EXPTIME die Menge aller Entscheidungsprobleme, die eine exponentielle Laufzeit haben. Mit anderen Worten: Jedes Problem in EXPTIME ist von einer deterministischen Turing-Maschine in O(2^p(n)) Zeit lösbar, wobei p(n) eine Polynomfunktion von n ist. Ein Entscheidungsproblem ist EXPTIME-komplett, wenn es in EXPTIME ist, und jedes Problem in EXPTIME hat eine Polynomialzeit-Vielfach-Reduktion zu ihm. Eine Reihe von Problemen ist als EXPTIME-komplett bekannt. Da gezeigt werden kann, dass P ≠ EXPTIME ist, liegen diese Probleme außerhalb von P und benötigen daher mehr als Polynomialzeit. Nach dem Zeithierarchie-Theorem können sie nicht in wesentlich weniger als exponentieller Zeit gelöst werden. Beispiele sind die Suche nach einer perfekten Strategie für Schachpositionen auf einem N × N-Brett und ähnliche Probleme für andere Brettspiele. ⓘ

Das Problem, den Wahrheitsgehalt einer Aussage in der Presburger Arithmetik zu bestimmen, erfordert sogar noch mehr Zeit. Fischer und Rabin bewiesen 1974, dass jeder Algorithmus, der die Wahrheit von Presburger-Aussagen der Länge n entscheidet, eine Laufzeit von mindestens $2^{2^{cn}}$ für eine Konstante c hat. Daher ist bekannt, dass das Problem mehr als exponentielle Laufzeit benötigt. Noch schwieriger sind die unentscheidbaren Probleme, wie z.B. das Halteproblem. Sie können von keinem Algorithmus vollständig gelöst werden, in dem Sinne, dass es für jeden bestimmten Algorithmus mindestens eine Eingabe gibt, für die dieser Algorithmus nicht die richtige Antwort liefert; er liefert entweder die falsche Antwort, beendet das Problem, ohne eine schlüssige Antwort zu geben, oder läuft ewig, ohne überhaupt eine Antwort zu liefern. ⓘ

Es ist auch möglich, andere Fragen als Entscheidungsprobleme zu betrachten. Eine solche Klasse, die aus Zählproblemen besteht, wird #P genannt: Während ein NP-Problem die Frage "Gibt es irgendwelche Lösungen?" stellt, fragt das entsprechende #P-Problem "Wie viele Lösungen gibt es?" Es ist klar, dass ein #P-Problem mindestens so schwer sein muss wie das entsprechende NP-Problem, da eine Zählung der Lösungen sofort zeigt, ob mindestens eine Lösung existiert, wenn die Zahl größer als Null ist. Überraschenderweise entsprechen einige vermeintlich schwierige #P-Probleme einfachen P-Problemen (zum Beispiel mit linearer Zeit). Bei diesen Problemen ist es sehr einfach festzustellen, ob es Lösungen gibt, aber es wird als sehr schwierig angesehen, deren Anzahl zu bestimmen. Viele dieser Probleme sind #P-komplett und gehören damit zu den schwierigsten Problemen in #P, da eine Lösung in Polynomialzeit für jedes dieser Probleme eine Lösung in Polynomialzeit für alle anderen #P-Probleme ermöglichen würde. ⓘ

Probleme in NP, von denen nicht bekannt ist, dass sie in P oder NP-komplett sind

1975 zeigte Richard E. Ladner, dass, wenn P ≠ NP ist, es Probleme in NP gibt, die weder in P noch NP-komplett sind. Solche Probleme werden NP-intermediate problems genannt. Das Graphen-Isomorphismus-Problem, das diskrete Logarithmus-Problem und das Integer-Faktorisierungs-Problem sind Beispiele für Probleme, die als NP-intermediate gelten. Sie gehören zu den wenigen NP-Problemen, von denen man weiß, dass sie nicht in P liegen oder NP-komplett sind. ⓘ

Das Graphen-Isomorphismus-Problem ist das rechnerische Problem der Bestimmung, ob zwei endliche Graphen isomorph sind. Ein wichtiges ungelöstes Problem in der Komplexitätstheorie ist die Frage, ob das Graphenisomorphie-Problem in P, NP-komplett oder NP-intermediär ist. Die Antwort ist nicht bekannt, aber es wird angenommen, dass das Problem zumindest nicht NP-komplett ist. Wenn das Problem der Graphenisomorphie NP-komplett ist, kollabiert die Polynomialzeithierarchie auf ihre zweite Ebene. Da man davon ausgeht, dass die Polynomhierarchie nicht auf eine endliche Ebene kollabiert, geht man davon aus, dass die Graphenisomorphie nicht NP-komplett ist. Der beste Algorithmus für dieses Problem, der auf László Babai zurückgeht, läuft in Quasi-Polynomialzeit. ⓘ

Das Integer-Faktorisierungsproblem ist das rechnerische Problem der Bestimmung der Primfaktorzerlegung einer gegebenen ganzen Zahl. Als Entscheidungsproblem formuliert, ist es das Problem, zu entscheiden, ob die Eingabe einen Faktor kleiner als k hat. Es ist kein effizienter Algorithmus zur ganzzahligen Faktorisierung bekannt, und diese Tatsache bildet die Grundlage mehrerer moderner kryptographischer Systeme, wie z. B. des RSA-Algorithmus. Das Problem der ganzzahligen Faktorisierung ist in NP und in co-NP (und sogar in UP und co-UP). Wenn das Problem NP-komplett ist, kollabiert die Polynomialzeithierarchie auf ihre erste Ebene (d. h. NP = co-NP). Der effizienteste bekannte Algorithmus für die Faktorisierung ganzer Zahlen ist das allgemeine Zahlenfeldsieb, das die erwartete Zeit ⓘ

$O\left(\exp \left(\left({\tfrac {64n}{9}}\log(2)\right)^{\frac {1}{3}}\left(\log(n\log(2))\right)^{\frac {2}{3}}\right)\right)$ ⓘ

für die Faktorisierung einer n-Bit-Ganzzahl benötigt. Der beste bekannte Quantenalgorithmus für dieses Problem, der Shor-Algorithmus, läuft jedoch in polynomialer Zeit, obwohl dies keinen Hinweis darauf gibt, wo das Problem in Bezug auf Nicht-Quantenkomplexitätsklassen liegt. ⓘ

Bedeutet P "einfach"?

Das Diagramm zeigt die Laufzeit in Abhängigkeit von der Problemgröße für ein Knapsack-Problem eines hochmodernen, spezialisierten Algorithmus. Die quadratische Anpassung legt nahe, dass die algorithmische Komplexität des Problems O((log(n))²) beträgt. ⓘ

Bei den obigen Ausführungen wurde davon ausgegangen, dass P "einfach" und "nicht in P" "schwierig" bedeutet. Diese Annahme ist als Cobham-These bekannt. Diese Annahme ist in der Komplexitätstheorie weit verbreitet und einigermaßen zutreffend; sie ist jedoch mit einigen Einschränkungen verbunden. ⓘ

Erstens ist sie in der Praxis nicht immer zutreffend. Ein theoretischer Polynomalgorithmus kann extrem große konstante Faktoren oder Exponenten haben, was ihn unpraktisch macht. Beispielsweise kann das Problem, ob ein Graph G H als Nebengruppe enthält, wobei H fest ist, in einer Laufzeit von O(n²) gelöst werden, wobei n die Anzahl der Knoten in G ist. Hinter der großen O-Notation verbirgt sich jedoch eine Konstante, die superexponentiell von H abhängt. $2\uparrow \uparrow (2\uparrow \uparrow (2\uparrow \uparrow (h/2)))$ (unter Verwendung von Knuths Pfeil-nach-oben-Schreibweise), wobei h die Anzahl der Scheitelpunkte in H ist. ⓘ

Andererseits kann es selbst dann, wenn sich ein Problem als NP-komplett erweist, und selbst wenn P ≠ NP ist, immer noch effektive Ansätze geben, um das Problem in der Praxis zu lösen. Es gibt Algorithmen für viele NP-komplette Probleme, wie das Knapsack-Problem, das Travelling-Salesman-Problem und das Boolesche Erfüllbarkeitsproblem, die viele reale Instanzen in angemessener Zeit optimal lösen können. Die empirische durchschnittliche Fallkomplexität (Zeit im Verhältnis zur Problemgröße) solcher Algorithmen kann überraschend niedrig sein. Ein Beispiel ist der Simplex-Algorithmus in der linearen Programmierung, der in der Praxis erstaunlich gut funktioniert; trotz seiner exponentiellen Worst-Case-Zeitkomplexität läuft er auf Augenhöhe mit den besten bekannten Polynomialzeit-Algorithmen. ⓘ

Schließlich gibt es Berechnungsarten, die nicht dem Turingmaschinenmodell entsprechen, auf dem P und NP definiert sind, wie z. B. Quantenberechnungen und randomisierte Algorithmen. ⓘ

Gründe für die Annahme von P ≠ NP oder P = NP

Cook formuliert das Problem in THE P VERSUS NP PROBLEM folgendermaßen um: Ist P = NP ?. Umfragen zufolge glauben die meisten Informatiker, dass P ≠ NP ist. Ein Hauptgrund für diese Überzeugung ist, dass nach jahrzehntelanger Untersuchung dieser Probleme niemand in der Lage war, einen Polynomialzeit-Algorithmus für eines der mehr als 3000 wichtigen bekannten NP-kompletten Probleme zu finden (siehe Liste der NP-kompletten Probleme). Diese Algorithmen wurden gesucht, lange bevor das Konzept der NP-Vollständigkeit überhaupt definiert wurde (die 21 NP-vollständigen Probleme von Karp, die zu den ersten gefundenen gehörten, waren zu dem Zeitpunkt, als sie sich als NP-vollständig erwiesen, allesamt bereits bekannte Probleme). Außerdem würde das Ergebnis P = NP viele andere verblüffende Ergebnisse implizieren, von denen man derzeit glaubt, dass sie falsch sind, wie z. B. NP = co-NP und P = PH. ⓘ

Es wird auch intuitiv argumentiert, dass die Existenz von Problemen, die schwer zu lösen sind, deren Lösungen aber leicht zu überprüfen sind, der realen Erfahrung entspricht.

Wenn P = NP wäre, dann wäre die Welt ein völlig anderer Ort, als wir sie gewöhnlich annehmen. Es gäbe keinen besonderen Wert von "kreativen Sprüngen", keine grundlegende Lücke zwischen dem Lösen eines Problems und dem Erkennen der Lösung, sobald sie gefunden ist.

- Scott Aaronson, UT Austin ⓘ

Andererseits sind einige Forscher der Meinung, dass die Überzeugung P ≠ NP übertrieben ist und dass Forscher auch Beweise für P = NP untersuchen sollten. Im Jahr 2002 wurden zum Beispiel diese Aussagen gemacht:

Das Hauptargument für P ≠ NP ist das völlige Fehlen grundlegender Fortschritte auf dem Gebiet der erschöpfenden Suche. Dies ist meiner Meinung nach ein sehr schwaches Argument. Der Raum der Algorithmen ist sehr groß und wir stehen erst am Anfang seiner Erforschung. [...] Die Lösung von Fermats letztem Satz zeigt auch, dass sehr einfache Fragen nur durch sehr tiefe Theorien gelöst werden können.

- Moshe Y. Vardi, Rice Universität

Das Festhalten an einer Spekulation ist kein guter Leitfaden für die Forschungsplanung. Man sollte bei jedem Problem immer beide Richtungen ausprobieren. Vorurteile haben dazu geführt, dass berühmte Mathematiker berühmte Probleme nicht lösen konnten, deren Lösung ihren Erwartungen zuwiderlief, obwohl sie alle erforderlichen Methoden entwickelt hatten.

- Anil Nerode, Cornell Universität ⓘ

Konsequenzen der Lösung

Einer der Gründe, warum das Problem so viel Aufmerksamkeit erregt, sind die Konsequenzen der möglichen Antworten. Jede der beiden Lösungsmöglichkeiten würde die Theorie enorm voranbringen und vielleicht auch enorme praktische Konsequenzen haben. ⓘ

P = NP

Ein Beweis, dass P = NP ist, könnte atemberaubende praktische Konsequenzen haben, wenn der Beweis zu effizienten Methoden für die Lösung einiger der wichtigen Probleme in NP führt. Die möglichen Folgen, sowohl positive als auch negative, ergeben sich daraus, dass verschiedene NP-komplette Probleme in vielen Bereichen von grundlegender Bedeutung sind. ⓘ

Es ist auch sehr gut möglich, dass ein Beweis nicht zu praktischen Algorithmen für NP-komplette Probleme führt. Die Formulierung des Problems erfordert nicht, dass das begrenzende Polynom klein oder sogar genau bekannt ist. Ein nicht-konstruktiver Beweis könnte zeigen, dass es eine Lösung gibt, ohne dass ein Algorithmus zu deren Erlangung oder eine spezifische Schranke angegeben wird. Selbst wenn der Beweis konstruktiv ist und ein explizites beschränkendes Polynom und algorithmische Details zeigt, könnte der Algorithmus in der Praxis nicht effizient genug sein, wenn das Polynom nicht sehr niederer Ordnung ist. In diesem Fall wäre der ursprüngliche Beweis vor allem für Theoretiker interessant, aber das Wissen, dass Lösungen in polynomialer Zeit möglich sind, würde sicherlich die Erforschung besserer (und möglicherweise praktischer) Methoden zu deren Erreichung anregen. ⓘ

Ein Beispiel für ein Gebiet, das durch eine Lösung, die P = NP zeigt, auf den Kopf gestellt werden könnte, ist die Kryptographie, die sich darauf stützt, dass bestimmte Probleme schwierig sind. Eine konstruktive und effiziente Lösung für ein NP-komplettes Problem wie 3-SAT würde die meisten bestehenden Kryptosysteme zerstören:

• Bestehende Implementierungen der Public-Key-Kryptografie, einer Grundlage für viele moderne Sicherheitsanwendungen wie sichere Finanztransaktionen über das Internet.
• Symmetrische Chiffren wie AES oder 3DES, die für die Verschlüsselung von Kommunikationsdaten verwendet werden.
• Kryptografisches Hashing, das Blockchain-Kryptowährungen wie Bitcoin zugrunde liegt und zur Authentifizierung von Software-Updates verwendet wird. Für diese Anwendungen muss das Problem, ein Vorabbild zu finden, das zu einem bestimmten Wert hasht, schwierig sein, um nützlich zu sein, und sollte idealerweise exponentielle Zeit erfordern. Wenn jedoch P = NP ist, dann kann das Finden eines Vorabbildes M in polynomieller Zeit durch Reduktion auf SAT erfolgen.

Diese müssten modifiziert oder durch informationstheoretisch sichere Lösungen ersetzt werden, die nicht auf P-NP-Ungleichheit beruhen. ⓘ

Andererseits hätte es enorme positive Auswirkungen, wenn viele derzeit mathematisch unlösbare Probleme handhabbar gemacht würden. So sind zum Beispiel viele Probleme im Bereich des Operations Research NP-komplett, wie einige Arten der ganzzahligen Programmierung und das Travelling-Salesman-Problem. Effiziente Lösungen für diese Probleme würden enorme Auswirkungen auf die Logistik haben. Viele andere wichtige Probleme, wie z. B. einige Probleme bei der Vorhersage von Proteinstrukturen, sind ebenfalls NP-komplett; wenn diese Probleme effizient lösbar wären, könnte dies zu erheblichen Fortschritten in den Biowissenschaften und der Biotechnologie führen. ⓘ

Aber solche Veränderungen mögen in ihrer Bedeutung verblassen im Vergleich zu der Revolution, die eine effiziente Methode zur Lösung NP-kompletter Probleme in der Mathematik selbst auslösen würde. Gödel bemerkte in seinen frühen Überlegungen zur rechnerischen Komplexität, dass eine mechanische Methode, die jedes Problem lösen könnte, die Mathematik revolutionieren würde:

Gäbe es tatsächlich eine Maschine mit φ(n) ∼ k ⋅ n (oder sogar ∼ k ⋅ n²), hätte dies Konsequenzen von größter Bedeutung. Es würde nämlich offensichtlich bedeuten, dass trotz der Unentscheidbarkeit des Entscheidungsproblems die Denkarbeit eines Mathematikers bei Ja-oder-Nein-Fragen vollständig durch eine Maschine ersetzt werden könnte. Schließlich müsste man nur die natürliche Zahl n so groß wählen, dass es keinen Sinn macht, weiter über das Problem nachzudenken, wenn die Maschine kein Ergebnis liefert.

Ähnlich sagt Stephen Cook (der nicht nur einen Beweis, sondern einen praktisch effizienten Algorithmus voraussetzt) ⓘ

... er würde die Mathematik verändern, indem er es einem Computer ermöglicht, einen formalen Beweis für jedes Theorem zu finden, das einen Beweis von angemessener Länge hat, da formale Beweise leicht in polynomieller Zeit erkannt werden können. Zu den Beispielproblemen könnten auch alle Probleme des CMI-Preises gehören. ⓘ

Forschungsmathematiker verbringen ihre ganze Karriere mit dem Versuch, Theoreme zu beweisen, und einige Beweise haben Jahrzehnte oder sogar Jahrhunderte gebraucht, um sie zu finden, nachdem Probleme formuliert worden waren - zum Beispiel dauerte es über drei Jahrhunderte, bis Fermats letzter Satz bewiesen war. Eine Methode, die garantiert Beweise für Theoreme findet, sollte es eine von "vernünftiger" Größe geben, würde diesen Kampf im Wesentlichen beenden. ⓘ

Donald Knuth hat erklärt, dass er zu der Überzeugung gelangt ist, dass P = NP ist, ist aber zurückhaltend, was die Auswirkungen eines möglichen Beweises angeht:

[...] wenn man sich eine Zahl M vorstellt, die endlich, aber unglaublich groß ist - wie etwa die Zahl 10↑↑↑↑3, die ich in meinem Aufsatz über den Umgang mit der Endlichkeit besprochen habe -, dann gibt es eine riesige Anzahl möglicher Algorithmen, die n^M bitweise oder Additions- oder Verschiebeoperationen auf n gegebenen Bits ausführen, und es ist wirklich schwer zu glauben, dass alle diese Algorithmen versagen. ⓘ Mein Hauptpunkt ist jedoch, dass ich nicht glaube, dass die Gleichheit P = NP sich als hilfreich erweisen wird, selbst wenn sie bewiesen wird, weil ein solcher Beweis fast sicher nicht konstruktiv sein wird.

ⓘ

Diagramm der Komplexitätsklassen unter der Voraussetzung, dass P ≠ NP. Die Existenz von Problemen, die innerhalb von NP, aber außerhalb von P und NP-komplett sind, wurde unter dieser Annahme durch das Ladner-Theorem nachgewiesen. ⓘ

P ≠ NP

Ein Beweis, der zeigt, dass P ≠ NP ist, hätte zwar nicht den praktischen rechnerischen Nutzen eines Beweises, dass P = NP ist, würde aber dennoch einen sehr bedeutenden Fortschritt in der Komplexitätstheorie darstellen und einen Leitfaden für zukünftige Forschungen bieten. Er würde es ermöglichen, auf formale Weise zu zeigen, dass viele gängige Probleme nicht effizient gelöst werden können, so dass die Aufmerksamkeit der Forscher auf Teillösungen oder Lösungen für andere Probleme gerichtet werden kann. Aufgrund des weit verbreiteten Glaubens an P ≠ NP hat ein Großteil dieser Konzentration der Forschung bereits stattgefunden. ⓘ

Auch P ≠ NP lässt die durchschnittliche Komplexität harter Probleme in NP noch offen. So ist es zum Beispiel möglich, dass SAT im schlimmsten Fall exponentielle Zeit benötigt, dass aber fast alle zufällig ausgewählten Instanzen effizient lösbar sind. Russell Impagliazzo hat fünf hypothetische "Welten" beschrieben, die sich aus verschiedenen möglichen Lösungen für die Frage der durchschnittlichen Komplexität ergeben könnten. Diese reichen von "Algorithmica", in der P = NP ist und Probleme wie SAT in allen Instanzen effizient gelöst werden können, bis zu "Cryptomania", in der P ≠ NP ist und die Erzeugung harter Instanzen von Problemen außerhalb von P einfach ist, mit drei Zwischenmöglichkeiten, die verschiedene mögliche Verteilungen der Schwierigkeit über Instanzen von NP-harten Problemen widerspiegeln. Die "Welt", in der P ≠ NP ist, aber alle Probleme in NP im durchschnittlichen Fall behandelbar sind, wird in dem Papier als "Heuristica" bezeichnet. Ein Workshop an der Princeton University im Jahr 2009 untersuchte den Status der fünf Welten. ⓘ

Ergebnisse zur Schwierigkeit von Beweisen

Obwohl das P = NP-Problem selbst trotz eines mit einer Million Dollar dotierten Preises und einer riesigen Menge engagierter Forschung offen bleibt, haben die Bemühungen zur Lösung des Problems zu mehreren neuen Techniken geführt. Einige der fruchtbarsten Forschungsarbeiten im Zusammenhang mit dem P = NP-Problem haben gezeigt, dass die vorhandenen Beweistechniken nicht ausreichen, um die Frage zu beantworten, was darauf hindeutet, dass neue technische Ansätze erforderlich sind. ⓘ

Ein weiterer Beweis für die Schwierigkeit des Problems ist, dass im Wesentlichen alle bekannten Beweistechniken in der Komplexitätstheorie in eine der folgenden Klassifizierungen fallen, von denen bekannt ist, dass sie nicht ausreichen, um zu beweisen, dass P ≠ NP ist:

Klassifizierung	Definition ⓘ
Relativierende Beweise	Stellen Sie sich eine Welt vor, in der jeder Algorithmus Anfragen an ein festes Unterprogramm, ein so genanntes Orakel, stellen darf (eine Blackbox, die eine feste Menge von Fragen in konstanter Zeit beantworten kann, z. B. eine Blackbox, die ein beliebiges Travelling-Salesman-Problem in einem Schritt löst), wobei die Laufzeit des Orakels nicht auf die Laufzeit des Algorithmus angerechnet wird. Die meisten Beweise (insbesondere die klassischen) gelten einheitlich in einer Welt mit Orakeln, unabhängig davon, was das Orakel tut. Diese Beweise werden als relativierend bezeichnet. 1975 zeigten Baker, Gill und Solovay, dass P = NP in Bezug auf einige Orakel ist, während P ≠ NP für andere Orakel gilt. Da relativierende Beweise nur Aussagen beweisen können, die in Bezug auf alle möglichen Orakel einheitlich wahr sind, zeigte dies, dass relativierende Techniken P = NP nicht auflösen können.
Natürliche Beweise	1993 definierten Alexander Razborov und Steven Rudich eine allgemeine Klasse von Beweistechniken für untere Schranken der Schaltkreiskomplexität, die so genannten natürlichen Beweise. Damals waren alle bis dahin bekannten Schaltungsuntergrenzen natürlich, und die Schaltungskomplexität galt als vielversprechender Ansatz zur Lösung von P = NP. Razborov und Rudich zeigten jedoch, dass, wenn Einwegfunktionen existieren, keine natürliche Beweismethode zwischen P und NP unterscheiden kann. Obwohl die Existenz von Einwegfunktionen nie formell bewiesen wurde, glauben die meisten Mathematiker, dass sie existieren, und ein Beweis ihrer Existenz wäre eine viel stärkere Aussage als P ≠ NP. Daher ist es unwahrscheinlich, dass natürliche Beweise allein P = NP auflösen können.
Algebrierende Beweise	Nach dem Baker-Gill-Solovay-Ergebnis wurden neue, nicht-relativierende Beweistechniken erfolgreich eingesetzt, um zu beweisen, dass IP = PSPACE ist. Im Jahr 2008 zeigten Scott Aaronson und Avi Wigderson jedoch, dass das wichtigste technische Werkzeug, das im IP = PSPACE-Beweis verwendet wird, die Arithmetisierung, ebenfalls nicht ausreicht, um P = NP zu lösen.

Diese Barrieren sind ein weiterer Grund, warum NP-komplette Probleme nützlich sind: Wenn ein Polynomialzeit-Algorithmus für ein NP-komplettes Problem gezeigt werden kann, würde dies das P = NP-Problem auf eine Weise lösen, die durch die obigen Ergebnisse nicht ausgeschlossen wird. ⓘ

Diese Hindernisse haben auch einige Informatiker dazu veranlasst, vorzuschlagen, dass das P-gegen-NP-Problem unabhängig von Standard-Axiomensystemen wie ZFC sein könnte (es kann innerhalb dieser Systeme weder bewiesen noch widerlegt werden). Die Interpretation eines Unabhängigkeitsresultats könnte sein, dass entweder kein Polynomialzeit-Algorithmus für ein NP-komplettes Problem existiert und ein solcher Beweis nicht in (z.B.) ZFC konstruiert werden kann, oder dass Polynomialzeit-Algorithmen für NP-komplette Probleme existieren können, es aber unmöglich ist, in ZFC zu beweisen, dass solche Algorithmen korrekt sind. Wenn jedoch mit Hilfe der derzeit bekannten Techniken gezeigt werden kann, dass das Problem auch mit sehr viel schwächeren Annahmen, die die Peano-Axiome (PA) für die ganzzahlige Arithmetik erweitern, nicht gelöst werden kann, dann würde es notwendigerweise für jedes NP-Problem Algorithmen mit nahezu polynomialer Zeit geben. Wenn man also glaubt (wie die meisten Komplexitätstheoretiker), dass es nicht für alle Probleme in NP effiziente Algorithmen gibt, dann folgt daraus, dass Unabhängigkeitsbeweise mit diesen Techniken nicht möglich sein können. Außerdem impliziert dieses Ergebnis, dass der Beweis der Unabhängigkeit von PA oder ZFC mit den derzeit bekannten Techniken nicht einfacher ist als der Beweis der Existenz von effizienten Algorithmen für alle Probleme in NP. ⓘ

Behauptete Lösungen

Obwohl das P-gegen-NP-Problem allgemein als ungelöst gilt, haben viele Amateur- und einige professionelle Forscher Lösungen behauptet. Gerhard J. Woeginger hat von 1986 bis 2016 eine Liste von 62 angeblichen Beweisen für P = NP zusammengestellt, von denen 50 Beweise für P ≠ NP waren, 2 Beweise, dass das Problem unbeweisbar ist, und ein Beweis, dass es unentscheidbar ist. Einige Versuche, das Problem P ≠ NP zu lösen, haben kurze Aufmerksamkeit in den Medien erregt, obwohl diese Versuche inzwischen widerlegt worden sind. ⓘ

Logische Charakterisierungen

Das P = NP-Problem kann als Ergebnis der Arbeit im Bereich der deskriptiven Komplexität in Form bestimmter Klassen von logischen Aussagen ausgedrückt werden. ⓘ

Man betrachte alle Sprachen endlicher Strukturen mit einer festen Signatur einschließlich einer linearen Ordnungsrelation. Alle derartigen Sprachen in P können in Logik erster Ordnung ausgedrückt werden, indem ein geeigneter Kombinator für die kleinsten Fixpunkte hinzugefügt wird. In Verbindung mit der Ordnung ermöglicht dies die Definition rekursiver Funktionen. Solange die Signatur neben der unterschiedenen Ordnungsrelation mindestens ein Prädikat oder eine Funktion enthält, so dass der Platzbedarf für die Speicherung solcher endlichen Strukturen tatsächlich polynomial zur Anzahl der Elemente in der Struktur ist, ist P genau dadurch charakterisiert. ⓘ

In ähnlicher Weise ist NP die Menge der Sprachen, die in der existenziellen Logik zweiter Ordnung ausgedrückt werden können, d. h. in der Logik zweiter Ordnung, die die universelle Quantifizierung über Relationen, Funktionen und Teilmengen ausschließt. Die Sprachen in der Polynomhierarchie, PH, entsprechen der gesamten Logik zweiter Ordnung. Die Frage "Ist P eine geeignete Teilmenge von NP?" kann also umformuliert werden als "Ist die existentielle Logik zweiter Ordnung in der Lage, Sprachen (endlicher linear geordneter Strukturen mit nichttrivialer Signatur) zu beschreiben, die die Logik erster Ordnung mit dem kleinsten Fixpunkt nicht beschreiben kann?". Das Wort "existentiell" kann sogar aus der vorherigen Charakterisierung gestrichen werden, da P = NP ist, wenn und nur wenn P = PH ist (da ersteres bedeuten würde, dass NP = co-NP ist, was wiederum impliziert, dass NP = PH ist). ⓘ

Polynomialzeit-Algorithmen

Es ist kein Algorithmus für ein NP-komplettes Problem bekannt, der in Polynomialzeit läuft. Es sind jedoch Algorithmen für NP-komplette Probleme bekannt, die die Eigenschaft haben, dass, wenn P = NP ist, der Algorithmus in polynomieller Zeit auf akzeptierenden Instanzen läuft (allerdings mit enormen Konstanten, was den Algorithmus unpraktisch macht). Diese Algorithmen gelten jedoch nicht als polynomiell, da ihre Laufzeiten für ablehnende Instanzen nicht polynomiell sind. Der folgende Algorithmus, der auf Levin zurückgeht (ohne Quellenangabe), ist ein solches Beispiel. Er akzeptiert korrekt die NP-komplette Sprache SUBSET-SUM. Er läuft in polynomieller Zeit auf Eingaben, die in SUBSET-SUM enthalten sind, wenn und nur wenn P = NP:

// Algorithmus, der die NP-komplette Sprache SUBSET-SUM akzeptiert.
//
// Dies ist ein Polynomialzeit-Algorithmus, wenn und nur wenn P = NP.
//
// "Polynomialzeit" bedeutet, dass er in Polynomialzeit "ja" zurückgibt, wenn
// die Antwort "ja" sein sollte, und läuft ewig, wenn sie "nein" ist.
//
// Eingabe: S = eine endliche Menge von ganzen Zahlen
// Ausgabe: "ja", wenn irgendeine Teilmenge von S die Summe 0 ergibt.
// Läuft ewig, sonst keine Ausgabe.
// Hinweis: "Programmnummer M" ist das Programm, das durch
// die ganze Zahl M in binärer Form schreibt und dann
// diese Bitfolge als ein Programm betrachtet
// Programm. Jedes mögliche Programm kann
// auf diese Weise erzeugt werden, obwohl die meisten
// aufgrund von Syntaxfehlern.
FOR K = 1...∞
  FOR M = 1...K
    Programm Nummer M für K Schritte mit der Eingabe S ausführen
    WENN das Programm eine Liste eindeutiger Ganzzahlen ausgibt
      UND die ganzen Zahlen sind alle in S
      UND die Summe der ganzen Zahlen ist 0
    DANN
      OUTPUT "ja" und HALT ⓘ

Wenn, und nur wenn, P = NP ist, dann ist dies ein Polynomialzeit-Algorithmus, der eine NP-komplette Sprache akzeptiert. "Akzeptieren" bedeutet, dass er in Polynomialzeit "ja"-Antworten gibt, aber ewig laufen darf, wenn die Antwort "nein" ist (auch bekannt als Halbalgorithmus). ⓘ

Dieser Algorithmus ist enorm unpraktisch, selbst wenn P = NP ist. Wenn das kürzeste Programm, das SUBSET-SUM in Polynomialzeit lösen kann, b Bits lang ist, wird der obige Algorithmus mindestens 2b - 1 andere Programme zuerst ausprobieren. ⓘ

Formale Definitionen

P und NP

Konzeptionell gesehen ist ein Entscheidungsproblem ein Problem, das als Eingabe eine Zeichenkette w über ein Alphabet Σ annimmt und "ja" oder "nein" ausgibt. Wenn es einen Algorithmus gibt (z. B. eine Turing-Maschine oder ein Computerprogramm mit unbeschränktem Speicher), der die richtige Antwort für eine beliebige Zeichenkette der Länge n in höchstens cnk Schritten erzeugen kann, wobei k und c Konstanten sind, die von der Zeichenkette unabhängig sind, dann sagen wir, dass das Problem in polynomialer Zeit gelöst werden kann, und wir ordnen es der Klasse P zu. Formal ist P definiert als die Menge aller Sprachen, die von einer deterministischen Turing-Maschine in polynomialer Zeit entschieden werden können. Das bedeutet,

$\mathbf {P} =\{L:L=L(M){\text{ for some deterministic polynomial-time Turing machine }}M\}$

wobei

$L(M)=\{w\in \Sigma ^{*}:M{\text{ accepts }}w\}$

und eine deterministische Polynomialzeit-Turingmaschine eine deterministische Turingmaschine M ist, die die folgenden zwei Bedingungen erfüllt:

1. M hält auf allen Eingaben w an und
2. es existiert $k\in N$ derart, dass $T_{M}(n)\in O(n^{k})$wobei sich O auf die große O-Notation bezieht und

$T_{M}(n)=\max\{t_{M}(w):w\in \Sigma ^{*},|w|=n\}$

$t_{M}(w)={\text{ number of steps }}M{\text{ takes to halt on input }}w.$ ⓘ

NP kann auf ähnliche Weise definiert werden, indem man nicht-deterministische Turing-Maschinen verwendet (der traditionelle Weg). Ein moderner Ansatz zur Definition von NP ist jedoch die Verwendung des Konzepts von Zertifikat und Verifizierer. Formal ist NP definiert als die Menge der Sprachen über einem endlichen Alphabet, die einen Verifizierer haben, der in polynomieller Zeit läuft, wobei der Begriff "Verifizierer" wie folgt definiert ist. ⓘ

Sei L eine Sprache über einem endlichen Alphabet, Σ. ⓘ

L ∈ NP wenn, und nur wenn, es eine binäre Relation gibt $R\subset \Sigma ^{*}\times \Sigma ^{*}$ und eine positive ganze Zahl k, so dass die beiden folgenden Bedingungen erfüllt sind:

1. Für alle $x\in \Sigma ^{*}$, $x\in L\Leftrightarrow \exists y\in \Sigma ^{*}$ so dass (x, y) ∈ R und $|y|\in O(|x|^{k})$; und
2. die Sprache $L_{R}=\{x\#y:(x,y)\in R\}$ über $\Sigma \cup \{\#\}$ ist durch eine deterministische Turingmaschine in polynomieller Zeit entscheidbar. ⓘ

Eine Turing-Maschine, die L_R entscheidet, wird als Verifizierer für L bezeichnet, und ein y, für das (x, y) ∈ R gilt, wird als Zertifikat für die Mitgliedschaft von x in L bezeichnet. ⓘ

Im Allgemeinen muss ein Verifizierer nicht polynomialzeitfähig sein. Damit L jedoch in NP ist, muss es einen Verifizierer geben, der in Polynomialzeit läuft. ⓘ

Beispiel

Sei

$\mathrm {COMPOSITE} =\left\{x\in \mathbb {N} \mid x=pq{\text{ for integers }}p,q>1\right\}$

$R=\left\{(x,y)\in \mathbb {N} \times \mathbb {N} \mid 1<y\leq {\sqrt {x}}{\text{ and }}y{\text{ divides }}x\right\}.$

Offensichtlich ist die Frage, ob ein gegebenes x ein Kompositum ist, äquivalent zu der Frage, ob x ein Mitglied von COMPOSITE ist. Es kann gezeigt werden, dass COMPOSITE ∈ NP ist, indem man prüft, ob es die obige Definition erfüllt (wenn wir natürliche Zahlen mit ihren binären Darstellungen identifizieren). ⓘ

COMPOSITE ist zufällig auch in P, was durch die Erfindung des AKS-Primatitätstests bewiesen wurde. ⓘ

NP-Vollständigkeit

Es gibt viele äquivalente Möglichkeiten, die NP-Vollständigkeit zu beschreiben. ⓘ

L sei eine Sprache über einem endlichen Alphabet Σ. ⓘ

L ist NP-komplett, wenn, und nur wenn, die folgenden zwei Bedingungen erfüllt sind:

1. L ∈ NP; und
2. jedes L in NP ist polynomial-zeit-reduzierbar auf L (geschrieben als $L'\leq _{p}L$), wobei $L'\leq _{p}L$ wenn, und nur wenn, die folgenden zwei Bedingungen erfüllt sind:
   1. Es existiert f : Σ* → Σ* derart, dass für alle w in Σ* gilt: $(w\in L'\Leftrightarrow f(w)\in L)$; und
   2. Es existiert eine Turing-Maschine mit Polynomialzeit, die mit f(w) auf ihrem Band bei jeder Eingabe w anhält. ⓘ

Oder: Wenn L ∈ NP ist und es ein anderes NP-komplettes Problem gibt, das polynomialzeitlich auf L reduziert werden kann, dann ist L NP-komplett. Dies ist eine gängige Methode, um zu beweisen, dass ein neues Problem NP-komplett ist. ⓘ

Populäre Kultur

Der Film Travelling Salesman von Regisseur Timothy Lanzone erzählt die Geschichte von vier Mathematikern, die von der US-Regierung beauftragt werden, das P-gegen-NP-Problem zu lösen. ⓘ

In der sechsten Folge der siebten Staffel der Simpsons, "Treehouse of Horror VI", taucht die Gleichung P=NP auf, kurz nachdem Homer versehentlich in die "dritte Dimension" gestolpert ist. ⓘ

In der zweiten Folge der zweiten Staffel von Elementary, "Solve for X", geht es um Sherlock und Watson, die die Morde an Mathematikern untersuchen, die versuchten, das Problem P gegen NP zu lösen. ⓘ

P und NP

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 $NP$ definiert werden kann, die viele Probleme von praktischem Interesse enthält, von denen man noch nicht weiß, ob sie in $P$ liegen. ⓘ

$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 $P$ eine Teilmenge von $NP$. ⓘ

Man kann $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. ⓘ