P-gegen-NP-Problem (P versus NP problem)

Das P-NP-Problem stellt eine bedeutende ungelöste Herausforderung innerhalb der theoretischen Informatik dar. Es stellt grundsätzlich die Frage, ob alle Probleme, für die eine Lösung schnell verifiziert werden kann, auch einer schnellen Lösung zugänglich sind.

Das P-NP-Problem ist ein großes ungelöstes Problem in der theoretischen Informatik. Informell wird gefragt, ob jedes Problem, dessen Lösung schnell verifiziert werden kann, auch schnell gelöst werden kann.

In diesem Zusammenhang bezeichnet „schnell“ die Existenz eines Algorithmus, der in der Lage ist, eine Aufgabe innerhalb der Polynomzeit, im Gegensatz zur exponentiellen Zeit, zu lösen. Dies impliziert, dass die für die Aufgabenerfüllung erforderliche Zeit durch eine Polynomfunktion relativ zur Eingabegröße des Algorithmus nach oben begrenzt wird. Die Kategorie der Probleme, die durch einen Algorithmus in polynomieller Zeit lösbar sind, wird als „P“ oder „Klasse P“ bezeichnet. Umgekehrt ist für bestimmte Probleme derzeit keine effiziente Methode zur Lösungsfindung bekannt; Wenn jedoch eine mögliche Lösung bereitgestellt wird, kann deren Richtigkeit schnell überprüft werden. Die Klasse von Problemen, bei denen eine Lösung in polynomialer Zeit verifiziert werden kann, wird als „NP“ bezeichnet, was „nichtdeterministische polynomiale Zeit“ bedeutet.

Die Lösung der P-gegen-NP-Frage würde feststellen, ob in polynomialer Zeit verifizierbare Probleme auch innerhalb polynomieller Zeit lösbar sind. Sollte P ≠ NP sein, eine weit verbreitete Vermutung, würde dies die Existenz von Problemen innerhalb von NP implizieren, deren Lösung rechnerisch schwieriger zu lösen als zu verifizieren ist; Insbesondere würden sie einer Lösung in polynomieller Zeit widerstehen, ihre Antworten könnten jedoch in polynomieller Zeit verifiziert werden.

Dieses Problem wird häufig als das kritischste ungelöste Problem in der Informatik bezeichnet. Über seine Bedeutung in der Computertheorie hinaus würde ein endgültiger Beweis, unabhängig von seinem Ergebnis, erhebliche Auswirkungen auf verschiedene Disziplinen haben, darunter Mathematik, Kryptographie, algorithmische Forschung, künstliche Intelligenz, Spieltheorie, Multimedia-Verarbeitung, Philosophie und Wirtschaftswissenschaften. Es ist eines der sieben Millennium-Preis-Probleme, die vom Clay Mathematics Institute ausgewählt wurden und für die erste genaue Lösung mit jeweils 1.000.000 US-Dollar dotiert sind.

Illustrativer Fall

Betrachten wir das folgende binäre Problem: Gegeben sei ein unvollständiges Sudoku-Gitter der Dimension n §1011§ ×<!-- × --> n §2122§ {\displaystyle n^2\times n^2}, gibt es mindestens eine gültige Lösung, sodass jede Zeile, jede Spalte und n ×<!-- × --> n {\displaystyle n\times n} Quadrat enthält die ganzen Zahlen von 1 bis n §6465§ {\displaystyle n^2}? Die Überprüfung positiver Beispiele dieses verallgemeinerten Sudoku-Problems ist unkompliziert, wenn eine mögliche Lösung bereitgestellt wird. Dennoch ist die Existenz eines Polynomzeitalgorithmus, der in der Lage ist, alle Fälle dieses Problems mit einer „Ja“- oder „Nein“-Antwort genau zu lösen, unbekannt. Folglich wird verallgemeinertes Sudoku in NP (schnell überprüfbar) eingeordnet, seine Einbeziehung in P (schnell lösbar) ist jedoch unbestimmt. (Eine verallgemeinerte Version von Sudoku muss in Betracht gezogen werden, da jedes Sudoku fester Größe nur eine endliche Anzahl möglicher Gitterkonfigurationen besitzt, sodass das Problem in P durch Tabellensuche lösbar ist.)

Historischer Kontext

Die formale Formulierung des P-gegen-NP-Problems wurde 1971 von Stephen Cook in seiner einflussreichen Veröffentlichung „The complexity of theorem proving procedure“ und anschließend, aber unabhängig davon, von Leonid Levin im Jahr 1973 vorgestellt.

Während das P-gegen-NP-Problem seine formale Definition im Jahr 1971 erhielt, gab es frühere Hinweise auf seine grundlegenden Probleme. Im Jahr 1955 korrespondierte der Mathematiker John Nash mit der National Security Agency und stellte die Theorie auf, dass der Rechenaufwand, der zum Entschlüsseln eines ausreichend komplexen Codes erforderlich sei, mit der Länge des Schlüssels exponentiell ansteigen würde. Wenn diese Hypothese begründet ist (was Nash selbst bezweifelt), würde sie die Bedingung nahelegen, die jetzt als P ≠ NP bezeichnet wird, vorausgesetzt, dass ein Kandidatenschlüssel innerhalb der Polynomzeit verifiziert werden kann. Darüber hinaus fragte Kurt Gödel 1956 in einem Brief an John von Neumann, ob die Beweisführung von Theoremen (derzeit als ko-NP-vollständig anerkannt) in quadratischer oder linearer Zeit durchgeführt werden könne, und schlug vor, dass eine solche Entwicklung die Automatisierung der Entdeckung mathematischer Beweise ermöglichen würde.

Hintergrund

Die rechnerische Komplexitätstheorie, ein Teilgebiet der Berechnungstheorie, untersucht die Ressourcen, die zur Lösung rechnerischer Probleme erforderlich sind, und konzentriert sich dabei insbesondere auf die Beziehung zwischen den Komplexitätsklassen P und NP. Zu den wichtigsten analysierten Ressourcen gehören Zeit, gemessen an der Anzahl der Rechenschritte, und Platz, quantifiziert durch Speichernutzung.

Für solche Analysen ist ein Rechenmodell unerlässlich, das typischerweise von einem Computer ausgeht, der deterministisch ist – das heißt, sein aktueller Zustand und seine Eingaben bestimmen eine einzelne mögliche Folgeaktion – und sequentiell, der Vorgänge nacheinander ausführt.

In diesem theoretischen Rahmen umfasst die Klasse P alle Entscheidungsprobleme (wie nachfolgend definiert), die von einer deterministischen sequentiellen Maschine innerhalb eines Zeitkomplexitätspolynoms zur Eingabegröße lösbar sind. Umgekehrt umfasst die Klasse NP alle Entscheidungsprobleme, für die positive Lösungen in polynomieller Zeit verifiziert werden können, sofern die richtigen Informationen vorliegen, oder äquivalent, deren Lösungen in polynomieller Zeit von einer nichtdeterministischen Maschine entdeckt werden können. Es ist offensichtlich, dass P ⊆ NP. Die bedeutendste ungelöste Frage in der theoretischen Informatik betrifft die genaue Beziehung zwischen diesen beiden Klassen:

Ist P äquivalent zu NP?

Seit 2001 hat William Gasarch drei Umfragen unter Forschern zur P ≠ NP-Vermutung und damit verbundenen Fragen durchgeführt. Der Anteil der Befragten, die P ≠ NP glaubten, stieg von 61 % im Jahr 2001 (100 Antworten) auf 83 % im Jahr 2011 (151 Antworten) und weiter auf 88 % im Jahr 2018 (124 Antworten). Unter den im Jahr 2018 befragten Experten waren 99 % der Meinung, dass P ≠ NP. Allerdings liefern diese Umfragen keine schlüssigen Beweise für oder gegen P = NP. Wie Gasarch es ausdrückte: „Dies bringt uns weder der Lösung von P=?NP näher noch dem Wissen, wann es gelöst wird, aber es versucht, ein objektiver Bericht über die subjektive Meinung dieser Ära zu sein.“

NP-Vollständigkeit

Das Konzept der NP-Vollständigkeit erweist sich als äußerst hilfreich bei der Beantwortung der P = NP-Frage. NP-vollständige Probleme sind solche, auf die jedes andere NP-Problem in polynomieller Zeit reduziert werden kann und deren Lösungen innerhalb polynomieller Zeit überprüfbar bleiben. Folglich kann jedes Problem innerhalb der NP-Klasse algorithmisch in ein NP-vollständiges Problem umgewandelt werden. Umgangssprachlich stellt ein NP-vollständiges Problem ein NP-Problem dar, das mindestens so rechenintensiv ist wie jedes andere Problem innerhalb der NP-Klasse.

NP-schwere Probleme werden dadurch charakterisiert, dass sie mindestens so rechenintensiv sind wie jedes andere Problem in NP; Insbesondere sind alle NP-Probleme in polynomieller Zeit auf sie reduzierbar. Entscheidend ist, dass NP-schwere Probleme nicht unbedingt Mitglieder der NP-Klasse sind, was bedeutet, dass ihre Lösungen möglicherweise nicht in polynomieller Zeit verifizierbar sind.

Zum Beispiel wird das boolesche Erfüllbarkeitsproblem durch das Cook-Levin-Theorem als NP-vollständig festgelegt, was impliziert, dass jede Instanz jedes Problems innerhalb von NP mechanisch in ein boolesches Erfüllbarkeitsproblem in polynomieller Zeit umgewandelt werden kann. Das Boolesche Erfüllbarkeitsproblem ist lediglich eines von zahlreichen NP-vollständigen Problemen. Eine wichtige Implikation ist, dass, wenn auch nur ein einziges NP-vollständiges Problem in P gefunden würde, P notwendigerweise gleich NP wäre. Dennoch wurde trotz der Bedeutung vieler NP-vollständiger Probleme noch kein effizienter Algorithmus für eines von ihnen entdeckt.

Während die Existenz von NP-vollständigen Problemen aus ihrer Definition möglicherweise nicht sofort ersichtlich ist, kann ein einfaches NP-vollständiges Problem konzeptualisiert werden: Gibt es eine gegebene Turing-Maschine M, die garantiert innerhalb der Polynomzeit terminiert, eine polynomgroße Eingabe, die M akzeptiert? Dieses Problem gehört zu NP, da die Überprüfung, ob M diese akzeptiert, bei gegebener Eingabe durch Simulation von M unkompliziert ist. Es ist NP-vollständig, da der Verifizierer für jede spezifische Instanz eines NP-Problems als Polynomzeitmaschine M dargestellt werden kann, die die zu verifizierende Lösung als Eingabe erhält. Folglich hängt die Bestimmung, ob es sich bei der Instanz um eine „Ja“- oder „Nein“-Instanz handelt, von der Existenz einer gültigen Eingabe ab.

Das Boolesche Erfüllbarkeitsproblem, allgemein als SAT bezeichnet, stellt das erste natürliche Problem dar, das nachweislich NP-vollständig ist. Diese Klassifizierung wird dem Cook-Levin-Theorem zugeschrieben, dessen Beweis komplizierte technische Spezifikationen zu Turing-Maschinen und deren Beziehung zur NP-Definition beinhaltet. Dennoch bot die Methode des Beweises durch Reduktion nach der Feststellung der NP-Vollständigkeit von SAT einen einfacheren Ansatz, um zahlreiche andere Probleme als NP-vollständig zu kategorisieren, wie beispielsweise das zuvor untersuchte Spiel Sudoku. In diesem Zusammenhang zeigt der Beweis, dass eine Lösung für Sudoku in polynomieller Zeit auch die Vervollständigung lateinischer Quadrate innerhalb polynomieller Zeit erleichtern könnte. Dies wiederum ergibt eine Lösung für das Problem der Partitionierung dreiteiliger Graphen in Dreiecke, die dann zur Auflösung der speziellen SAT-Instanz namens 3-SAT verwendet werden könnte, wodurch eine Lösung für die allgemeine boolesche Erfüllbarkeit bereitgestellt wird. Folglich führt eine Polynomzeitauflösung für Sudoku durch eine Folge mechanischer Transformationen zu einer Polynomzeitlösung für die Erfüllbarkeit, die dann zur Lösung jedes anderen NP-Problems in Polynomzeit verwendet werden kann. Durch solche Transformationsprozesse lässt sich eine Vielzahl scheinbar unterschiedlicher Probleme gegenseitig reduzieren, wodurch sie rechnerisch gleichwertig werden.

Probleme mit erhöhtem Schwierigkeitsgrad

Während die Äquivalenz von P und NP eine ungelöste Frage bleibt, ist die Existenz von Problemen außerhalb der Klasse P endgültig erwiesen. Analog zur Definition der Klasse P durch polynomiale Laufzeit umfasst die Klasse EXPTIME alle Entscheidungsprobleme, die durch exponentielle Laufzeit gekennzeichnet sind. Insbesondere ist jedes Problem innerhalb von EXPTIME durch eine deterministische Turingmaschine in O(2^p(n)) Zeit lösbar, wobei p(n) eine Polynomfunktion von n bezeichnet. Ein Entscheidungsproblem wird als EXPTIME-vollständig bezeichnet, wenn es zu EXPTIME gehört und jedes Problem innerhalb von EXPTIME über eine polynomiellzeitige Viele-Eins-Reduktion darauf reduziert werden kann. Zahlreiche Probleme werden als EXPTIME-vollständig erkannt. Vorausgesetzt, dass P ≠ EXPTIME rigoros nachgewiesen werden kann, liegen diese Probleme außerhalb von P und erfordern folglich mehr als polynomiale Zeit für ihre Lösung. Tatsächlich können sie nach dem Zeithierarchietheorem nicht in wesentlich kürzerer Zeit als der exponentiellen Zeit gelöst werden. Anschauliche Beispiele hierfür sind die Bestimmung einer optimalen Strategie für Schachpositionen auf einem N × N-Brett und analoge Herausforderungen in anderen Brettspielen.

Der Rechenaufwand für die Feststellung der Wahrheit einer Aussage in der Presburger-Arithmetik ist noch erheblicher. Fischer und Rabin zeigten 1974, dass jeder Algorithmus, der die Wahrheit von Presburger-Aussagen der Länge n bestimmen soll, eine Mindestlaufzeit von mindestens aufweist §910§ §1314§ c n {\displaystyle 2^{2^{cn}}} für eine bestimmte Konstante c. Daher ist bekannt, dass dieses Problem eine superexponentielle Laufzeit erfordert. Noch größere Herausforderungen stellen die unentscheidbaren Probleme dar, wie zum Beispiel das Halteproblem. Diese Probleme können von keinem Algorithmus vollständig gelöst werden, was bedeutet, dass es für jeden einzelnen Algorithmus mindestens eine Eingabe gibt, für die er nicht die richtige Antwort liefern kann; Es kann zu einem fehlerhaften Ergebnis führen, ohne schlüssige Entscheidung beendet werden oder dauerhaft ausgeführt werden, ohne dass irgendeine Ausgabe generiert wird.

Über Entscheidungsprobleme hinaus können auch andere Kategorien von Fragen berücksichtigt werden. Eine solche Klasse, die Zählprobleme umfasst, wird als #P bezeichnet: Während ein NP-Problem fragt: „Gibt es Lösungen?“, fragt das entsprechende #P-Problem: „Wie viele Lösungen gibt es?“. Offensichtlich muss ein #P-Problem mindestens so rechenintensiv sein wie sein entsprechendes NP-Problem, vorausgesetzt, dass eine genaue Anzahl von Lösungen sofort die Existenz mindestens einer Lösung anzeigt, wenn die Anzahl Null überschreitet. Überraschenderweise entsprechen bestimmte #P-Probleme, die allgemein als schwierig gelten, rechnerisch behandelbaren (z. B. linearen Zeit-)P-Problemen. Für diese spezifischen Probleme ist die Bestimmung der Existenz von Lösungen einfach, die Quantifizierung ihrer Anzahl gilt jedoch als außerordentlich schwierig. Viele dieser Probleme sind #P-vollständig und gehören damit zu den schwierigsten Problemen in #P, da eine polynomielle Lösung für jedes dieser Probleme polynomielle Lösungen für alle anderen #P-Probleme ermöglichen würde.

Zwischenprobleme innerhalb von NP

Richard E. Ladner zeigte 1975, dass, wenn P ≠ NP, eine Klasse von Problemen innerhalb von NP existiert, die weder in polynomieller Zeit (P) lösbar noch NP-vollständig sind. Diese werden als NP-intermediäre Probleme bezeichnet. Prominente Beispiele, von denen angenommen wird, dass sie in diese Kategorie fallen, sind das Problem des Graphisomorphismus, das Problem des diskreten Logarithmus und das Problem der ganzzahligen Faktorisierung. Diese stellen eine ausgewählte Gruppe von NP-Problemen dar, deren Klassifizierung als entweder P oder NP-vollständig unbestimmt bleibt.

Das Graphisomorphismusproblem beinhaltet die rechnerische Bestimmung, ob zwei endliche Graphen strukturell identisch sind. Eine wichtige ungelöste Frage in der Komplexitätstheorie betrifft, ob dieses Problem zu P gehört, NP-vollständig oder NP-intermediär ist. Obwohl die genaue Klassifizierung unbekannt ist, wird allgemein angenommen, dass das Problem nicht NP-vollständig ist. Wenn der Graphisomorphismus NP-vollständig wäre, würde dies einen Zusammenbruch der polynomialen Zeithierarchie auf ihre zweite Ebene bedeuten. Angesichts der vorherrschenden Überzeugung, dass die Polynomhierarchie nicht auf eine endliche Ebene kollabiert, legt der Konsens nahe, dass der Graphisomorphismus nicht NP-vollständig ist. Der derzeit effizienteste Algorithmus für dieses Problem, entwickelt von László Babai, arbeitet in quasi-polynomialer Zeit.

Das Ganzzahlfaktorisierungsproblem ist definiert als die Rechenaufgabe, die Primfaktoren einer gegebenen ganzen Zahl zu identifizieren. Wenn es als Entscheidungsproblem formuliert wird, muss ermittelt werden, ob eine eingegebene Ganzzahl einen Faktor kleiner als k besitzt. Derzeit ist kein effizienter Algorithmus zur Ganzzahlfaktorisierung bekannt, eine Eigenschaft, die die Sicherheit mehrerer moderner kryptografischer Systeme, einschließlich des RSA-Algorithmus, untermauert. Dieses Problem wird sowohl in NP als auch in Co-NP und sogar in UP und Co-UP klassifiziert. Sollte sich das ganzzahlige Faktorisierungsproblem als NP-vollständig erweisen, würde dies zum Zusammenbruch der polynomialen Zeithierarchie auf ihre erste Ebene führen, was impliziert, dass NP = co-NP. Der effizienteste klassische Algorithmus zur Ganzzahlfaktorisierung ist das allgemeine Zahlenfeldsieb, das eine erwartete Zeitkomplexität von

58§ §5960§ ( Protokoll ⁡ ( n Protokoll ⁡ ( §8586§ ) ) ) §9798§ §99100§ ) ) {\displaystyle 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)}

um eine n-Bit-Ganzzahl zu faktorisieren. Im Gegensatz dazu arbeitet Shors Algorithmus, der effizienteste bekannte Quantenalgorithmus für dieses Problem, in polynomieller Zeit. Dieses Quantenergebnis liefert jedoch keinen Einblick in die Klassifizierung des Problems innerhalb Nicht-Quanten-Komplexitätsklassen.

Die Beziehung zwischen P und behandelbaren Problemen

Der vorangegangene Diskurs geht davon aus, dass Probleme innerhalb von P als „einfach“ oder lösbar angesehen werden, während Probleme, die nicht in P enthalten sind, als „schwierig“ oder unlösbar gelten. Diese Grundannahme wird offiziell als Cobhams These anerkannt. Obwohl diese Annahme in der Komplexitätstheorie weit verbreitet ist, ist sie nicht ohne Einschränkungen.

Erstens kann die praktische Anwendbarkeit solcher Algorithmen eingeschränkt sein. Ein theoretisch polynomieller Algorithmus könnte über übermäßig große konstante Faktoren oder Exponenten verfügen, was ihn für den Einsatz in der Praxis unpraktisch macht. Beispielsweise kann die Bestimmung, ob ein Graph G H als Minor enthält, bei gegebenem festen Graphen H innerhalb einer Laufzeitkomplexität von O(n§1011§) erfolgen, wobei n die Anzahl der Eckpunkte in G darstellt. Dennoch verdeckt die große O-Notation einen konstanten Faktor, der eine superexponentielle Abhängigkeit von H aufweist. Diese Konstante überschreitet §2425§ ↑ ↑ ( §3233§ ↑ ↑ ( §4041§ ↑ ↑ ( h / §5455§ ) ) ) {\displaystyle 2\uparrow \uparrow (2\uparrow \uparrow (2\uparrow \uparrow (h/2))) (ausgedrückt mit Knuths Aufwärtspfeil-Notation), wobei h die Anzahl der Eckpunkte in H bezeichnet.

Umgekehrt kann es auch dann noch praktische und effektive Lösungsmethoden geben, wenn ein Problem als NP-vollständig klassifiziert wird und sogar unter der Annahme, dass P ≠ NP. Zahlreiche Algorithmen für verschiedene NP-vollständige Probleme, darunter das Rucksackproblem, das Problem des Handlungsreisenden und das Boolesche Erfüllbarkeitsproblem, sind in der Lage, innerhalb praktischer Zeitrahmen optimale Lösungen für viele reale Fälle zu erzielen. Die beobachtete durchschnittliche Fallkomplexität (im Verhältnis zur Ausführungszeit zur Problemgröße) kann für diese Algorithmen bemerkenswert niedrig sein. Ein bemerkenswertes Beispiel ist der Simplex-Algorithmus in der linearen Programmierung, der eine außergewöhnliche praktische Leistung zeigt; Trotz seiner exponentiellen Zeitkomplexität im ungünstigsten Fall ist seine Betriebseffizienz mit der der effektivsten polynomialen Zeitalgorithmen vergleichbar.

Schließlich stimmen bestimmte Rechenparadigmen wie Quantenberechnung und randomisierte Algorithmen nicht mit dem Turing-Maschinenmodell überein, auf dem die Klassen P und NP grundsätzlich definiert sind.

Argumente, die P ≠ NP oder P = NP unterstützen

In The P Versus NP Problem formuliert Cook die Kernfrage neu als „Ist P = NP?“ Umfragedaten zeigen, dass die Mehrheit der Informatiker der Meinung ist, dass P ≠ NP. Eine Hauptbegründung für diese Überzeugung ergibt sich aus der Tatsache, dass trotz jahrzehntelanger Forschung zu diesen Herausforderungen kein polynomieller Algorithmus für eines der über 3.000 bedeutenden bekannten NP-vollständigen Probleme entdeckt wurde. Solche Algorithmen wurden schon lange vor der formalen Definition der NP-Vollständigkeit aktiv gesucht; Beispielsweise waren die 21 NP-vollständigen Probleme von Karp, die zu den frühesten identifizierten gehörten, bereits etablierte Probleme, als ihre NP-Vollständigkeit nachgewiesen wurde. Darüber hinaus würde eine Auflösung von P = NP zahlreiche weitere überraschende Konsequenzen nach sich ziehen, die derzeit als unwahrscheinlich gelten, darunter NP = co-NP und P = PH.

Darüber hinaus legt ein intuitives Argument nahe, dass die Existenz von Problemen, die schwer zu lösen, aber einfach zu überprüfen sind, mit praktischen Beobachtungen aus der realen Welt übereinstimmt.

Wenn P = NP, dann wäre die Welt ein völlig anderer Ort, als wir normalerweise annehmen. Es gäbe keinen besonderen Wert in „kreativen Sprüngen“, es gäbe keine grundlegende Lücke zwischen der Lösung eines Problems und dem Erkennen der Lösung, sobald sie gefunden wurde.

Umgekehrt behaupten einige Forscher, dass die Annahme von P ≠ NP zu sicher sei, und befürworten die Untersuchung möglicher Beweise für P = NP. Beispielsweise wurden im Jahr 2002 folgende Aussagen geäußert:

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

An einer Spekulation festzuhalten ist kein guter Leitfaden für die Forschungsplanung. Bei jedem Problem sollte man immer beide Richtungen ausprobieren. Vorurteile haben dazu geführt, dass es berühmten Mathematikern nicht gelang, berühmte Probleme zu lösen, deren Lösung ihren Erwartungen widersprach, obwohl sie alle erforderlichen Methoden entwickelt hatten.

DLIN versus NLIN

Durch Ersetzen von „linearer Zeit auf einer Multiband-Turing-Maschine“ durch „polynomiale Zeit“ innerhalb der Definitionen von P und NP werden die Klassen DLIN und NLIN abgeleitet. Es wurde festgestellt, dass DLIN ≠ NLIN.

Auswirkungen einer Lösung

Die große Aufmerksamkeit, die diesem Problem zuteil wird, ergibt sich aus den tiefgreifenden Auswirkungen seiner möglichen Lösungen. Eine endgültige Antwort, unabhängig von der Richtung, würde das theoretische Verständnis erheblich voranbringen und könnte enorme praktische Auswirkungen haben.

P = NP

Der Nachweis, dass P = NP ist, könnte zu bemerkenswerten praktischen Ergebnissen führen, insbesondere wenn ein solcher Beweis effiziente Methoden zur Lösung kritischer Probleme innerhalb der NP-Komplexitätsklasse ermöglicht. Die potenziellen Auswirkungen, die sowohl vorteilhafte als auch nachteilige Aspekte umfassen, ergeben sich aus der grundlegenden Rolle zahlreicher NP-vollständiger Probleme in verschiedenen Disziplinen.

Umgekehrt muss ein Beweis nicht unbedingt in praktische Algorithmen für NP-vollständige Probleme umgesetzt werden. Die Definition des Problems erfordert kein kleines oder explizit bekanntes Begrenzungspolynom. Ein nicht-konstruktiver Beweis könnte beispielsweise die Existenz einer Lösung nachweisen, ohne einen Algorithmus für ihre Ableitung detailliert anzugeben oder eine genaue Grenze anzugeben. Selbst mit einem konstruktiven Beweis, der ein explizites Begrenzungspolynom und algorithmische Besonderheiten liefert, könnte sich der Algorithmus für die praktische Anwendung als ineffizient erweisen, wenn die Ordnung des Polynoms nicht ausreichend niedrig ist. In einem solchen Szenario würde der erste Beweis in erster Linie Theoretiker beschäftigen, doch die Bestätigung polynomialer Zeitlösungen würde zweifellos weitere Forschungen zu effektiveren und potenziell praktischen Methoden anregen.

Eine Lösung, die P = NP nachweist, könnte das Gebiet der Kryptographie, die von Natur aus von der rechnerischen Unlösbarkeit spezifischer Probleme abhängt, grundlegend verändern. Ein konstruktiver und effizienter Algorithmus für ein NP-vollständiges Problem wie 3-SAT würde die Sicherheit der meisten aktuellen Kryptosysteme gefährden, darunter:

• Aktuelle Implementierungen der Public-Key-Kryptographie, die die Grundlage zahlreicher moderner Sicherheitsanwendungen bilden, einschließlich sicherer Finanztransaktionen, die über das Internet durchgeführt werden.
• Symmetrische Chiffren wie AES oder 3DES, die zur Verschlüsselung von Kommunikationsdaten eingesetzt werden.
• Kryptografisches Hashing, das als zugrunde liegender Mechanismus für Blockchain-basierte Kryptowährungen wie Bitcoin dient und zur Authentifizierung von Software-Updates verwendet wird. In diesen Kontexten muss der Prozess der Entdeckung eines Vorbilds, das auf einen bestimmten Wert hasht, rechenintensiv sein und im Idealfall eine exponentielle Zeit in Anspruch nehmen. Wenn P = NP ist, könnte diese Aufgabe jedoch in polynomieller Zeit durch eine Reduktion auf SAT gelöst werden.

Folglich müssten diese Systeme entweder modifiziert oder durch informationstheoretisch sichere Alternativen ersetzt werden, die nicht P ≠ NP voraussetzen.

Darüber hinaus würden sich erhebliche Vorteile ergeben, wenn zahlreiche derzeit mathematisch unlösbare Probleme beherrschbar gemacht würden. Beispielsweise sind zahlreiche Probleme im Operations Research, darunter verschiedene Formen der Ganzzahlprogrammierung und das Problem des Handlungsreisenden, NP-vollständig. Effiziente Lösungen für diese Herausforderungen würden tiefgreifende Auswirkungen auf die Logistik haben. In ähnlicher Weise sind auch viele andere kritische Probleme, wie sie bei der Vorhersage der Proteinstruktur auftreten, NP-vollständig; Die effiziente Lösung dieser Probleme könnte Fortschritte in den Biowissenschaften und der Biotechnologie erheblich vorantreiben.

Diese Transformationen könnten jedoch im Vergleich zu der tiefgreifenden Revolution, die effiziente Lösungen für NP-vollständige Probleme in der Mathematik selbst auslösen würden, verblassen. Gödel stellte in seinen ersten Überlegungen zur Rechenkomplexität fest, dass eine mechanische Methodik, die jedes Problem lösen kann, die Mathematik grundlegend verändern würde:

Wenn es tatsächlich eine Maschine gäbe, die mit φ(n) ∼ k⋅n (oder sogar ∼ k⋅n§1112§) arbeitet, wären die Implikationen von größter Bedeutung. Insbesondere würde es eindeutig bedeuten, dass trotz der Unentscheidbarkeit des Entscheidungsproblems die intellektuellen Bemühungen eines Mathematikers im Zusammenhang mit Ja-oder-Nein-Anfragen vollständig durch eine Maschine ersetzt werden könnten. Letztlich müsste man lediglich eine ausreichend große natürliche Zahl n wählen, so dass, wenn die Maschine kein Ergebnis liefert, eine weitere Betrachtung des Problems zwecklos wird.

In ähnlicher Weise stellt Stephen Cook fest, der nicht nur einen Beweis, sondern auch einen praktisch effizienten Algorithmus postuliert:

... es würde die Mathematik revolutionieren, indem es einem Computer ermöglicht, einen formalen Beweis für jeden Satz zu finden, der einen Beweis von angemessener Länge besitzt, vorausgesetzt, formale Beweise sind in polynomieller Zeit leicht verifizierbar. Anschauliche Probleme könnten alle CMI-Preisprobleme umfassen.

Forschungsmathematiker widmen ihr Berufsleben dem Bemühen, Theoreme zu beweisen, wobei einige Beweise Jahrzehnte oder sogar Jahrhunderte nach der ursprünglichen Formulierung der Probleme benötigen, um sie zu beweisen – zum Beispiel benötigte die Demonstration von Fermats letztem Satz über drei Jahrhunderte. Eine Methode, mit der sich garantiert ein Beweis ermitteln lässt, vorausgesetzt, es existiert ein Beweis von „angemessener“ Größe, würde diese langwierige intellektuelle Herausforderung grundsätzlich abschließen.

Donald Knuth hat die Überzeugung zum Ausdruck gebracht, dass P = NP ist, behält jedoch Vorbehalte hinsichtlich der Implikationen eines möglichen Beweises bei.

[...] Unter Berücksichtigung einer endlichen, aber außergewöhnlich großen Zahl wie M – am Beispiel von 10 ↑ ↑ ↑ ↑ 3, wie in seinem Aufsatz „Coping with Finiteness“ untersucht – gibt es eine große Vielzahl von Algorithmen, die n^M bitweise, Additions- oder Verschiebungsoperationen an n angegebenen Bits ausführen, was sie sehr hoch macht Es ist unwahrscheinlich, dass sich jeder dieser Algorithmen als erfolglos erweisen würde. Dennoch ist seine Hauptbehauptung, dass die P = NP-Gleichheit, selbst wenn sie nachgewiesen wird, wahrscheinlich keinen praktischen Nutzen bringt, da ein solcher Beweis mit ziemlicher Sicherheit nicht konstruktiv wäre.

Der Satz P ≠ NP.

Ein Beweis für P ≠ NP würde nicht die direkten praktischen Rechenvorteile eines Beweises für P = NP bieten; Dies würde jedoch einen erheblichen Fortschritt in der rechnerischen Komplexitätstheorie darstellen und für nachfolgende Untersuchungen von Nutzen sein. Ein solcher Beweis würde belegen, dass zahlreiche vorherrschende Probleme nicht effizient gelöst werden können, wodurch die Bemühungen der Forscher auf Teillösungen oder alternative Problembereiche ausgerichtet werden könnten. Angesichts des vorherrschenden Konsenses zugunsten von P ≠ NP hat ein wesentlicher Teil dieser Neuausrichtung der Forschung bereits stattgefunden.

Der Satz P ≠ NP löst nicht die Frage der durchschnittlichen Fallkomplexität für schwierige Probleme innerhalb von NP. Beispielsweise könnte SAT im schlimmsten Fall eine exponentielle Zeit erfordern, dennoch könnten nahezu alle zufällig ausgewählten Fälle effizient lösbar sein. Russell Impagliazzo hat fünf hypothetische „Welten“ beschrieben, die aus verschiedenen Lösungen für die Untersuchung der Komplexität durchschnittlicher Fälle entstehen könnten. Diese reichen von „Algorithmica“, wo P = NP und Probleme wie SAT in allen Instanzen effizient lösbar sind, bis hin zu „Cryptomania“, wo P ≠ NP und die Generierung schwieriger Instanzen für Probleme außerhalb von P unkompliziert ist. Es gibt auch drei Zwischenmöglichkeiten, die unterschiedliche Schwierigkeitsverteilungen bei NP-schweren Problemen widerspiegeln. Das Szenario, in dem P ≠ NP ist, alle Probleme innerhalb von NP jedoch im Durchschnitt beherrschbar sind, wird in der referenzierten Veröffentlichung als „Heuristica“ bezeichnet. Ein Workshop an der Princeton University im Jahr 2009 untersuchte den Status dieser fünf Konzeptwelten.

Ergebnisse zur Beweisschwierigkeit.

Obwohl das P = NP-Problem selbst weiterhin eine ungelöste Herausforderung darstellt, haben Versuche zur Lösung dieses Problems trotz eines Millionen-Dollar-Preises und umfangreicher engagierter Forschung zahlreiche neuartige Techniken hervorgebracht. Bemerkenswerterweise haben einige der produktivsten Untersuchungen zum P = NP-Problem die Unzulänglichkeit aktueller Beweismethoden zur Beantwortung dieser Frage aufgezeigt und damit die Notwendigkeit neuartiger technischer Ansätze aufgezeigt.

Um die inhärente Schwierigkeit dieses Problems weiter zu unterstreichen, werden praktisch alle etablierten Beweistechniken innerhalb der rechnerischen Komplexitätstheorie in Klassifikationen eingeteilt, die ausnahmslos nicht ausreichen, um P ≠ NP zu beweisen.

Diese identifizierten Hindernisse unterstreichen den Nutzen NP-vollständiger Probleme. Konkret: Wenn ein polynomialer Zeitalgorithmus für ein NP-vollständiges Problem demonstriert werden sollte, würde er das P = NP-Problem mit einer Methode lösen, die durch die oben genannten Erkenntnisse nicht ausgeschlossen ist.

Diese Hindernisse haben einige Informatiker zu der Hypothese veranlasst, dass das P-NP-Problem möglicherweise unabhängig von Standardaxiomatiksystemen wie ZFC ist, was bedeutet, dass es innerhalb dieser Rahmenwerke weder bewiesen noch widerlegt werden kann. Ein solches Unabhängigkeitsergebnis könnte zwei Möglichkeiten nahelegen: entweder P ≠ NP, und diese Behauptung ist (zum Beispiel) innerhalb von ZFC nicht beweisbar, oder P = NP, aber die Korrektheit aller Polynomzeitalgorithmen ist innerhalb von ZFC nicht beweisbar. Wäre das Problem umgekehrt selbst unter wesentlich schwächeren Annahmen, wie z. B. Erweiterungen der Peano-Axiome für die Ganzzahlarithmetik, unentscheidbar, dann gäbe es für alle NP-Probleme Algorithmen, die sich der Polynomialzeit annähern. Wenn man also annimmt, wie es unter Komplexitätstheoretikern üblich ist, dass bestimmte NP-Probleme keine effizienten Algorithmen haben, werden Unabhängigkeitsbeweise mit solchen Techniken nicht durchführbar. Dies impliziert weiter, dass der Nachweis der Unabhängigkeit von Peano-Axiomen (PA) oder ZFC unter Verwendung aktueller Methoden nicht weniger schwierig ist als der Nachweis der Existenz effizienter Algorithmen für alle NP-Probleme.

Logische Charakterisierungen.

Das P = NP-Problem lässt sich in Form spezifischer Klassen logischer Aussagen umformulieren, eine Entwicklung, die aus der Forschung zur deskriptiven Komplexität stammt.

Im Kontext von Sprachen für endliche Strukturen, die eine feste Signatur besitzen, die eine lineare Ordnungsrelation beinhaltet, sind alle in P klassifizierten Sprachen mit Logik erster Ordnung, ergänzt durch einen geeigneten Kleinstkommakombinator, ausdrückbar. Dieses Framework ermöglicht in Kombination mit der Ordnungsrelation die Definition rekursiver Funktionen. Vorausgesetzt, dass die Signatur mindestens ein Prädikat oder eine Funktion enthält, die über die angegebene Ordnungsbeziehung hinausgeht und sicherstellt, dass die Speicheranforderungen für diese endlichen Strukturen in Bezug auf ihre Elementanzahl polynomial sind, charakterisiert diese Formulierung die Komplexitätsklasse P genau.

Analog dazu umfasst die Komplexitätsklasse NP Sprachen, die durch existenzielle Logik zweiter Ordnung ausgedrückt werden können. Dabei handelt es sich um eine Logik zweiter Ordnung, die speziell darauf beschränkt ist, eine universelle Quantifizierung über Beziehungen, Funktionen und Teilmengen wegzulassen. Die Sprachen, aus denen die Polynomhierarchie (PH) besteht, entsprechen dem vollen Umfang der Logik zweiter Ordnung. Folglich kann die Untersuchung, ob P eine echte Teilmenge von NP darstellt, umformuliert werden als: „Kann existenzielle Logik zweiter Ordnung Sprachen beschreiben (die sich auf endliche, linear geordnete Strukturen mit nicht trivialen Signaturen beziehen), die über die Beschreibungskapazität der Logik erster Ordnung hinausgehen, die durch einen Operator mit dem kleinsten Fixpunkt erweitert wird?“ Darüber hinaus kann der Begriff „existentiell“ in der vorherigen Charakterisierung weggelassen werden, da P = NP genau dann gilt, wenn P = PH (da P = NP NP = Co-NP implizieren würde, was anschließend NP = PH nach sich zieht).

Algorithmen, die in polynomialer Zeit arbeiten

Derzeit ist kein Algorithmus bekannt, der ein NP-vollständiges Problem innerhalb der Polynomzeit löst. Dennoch gibt es bestimmte Algorithmen für NP-vollständige Probleme, die unter der Annahme P = NP in polynomialer Zeit für die Annahme von Instanzen ausgeführt würden, allerdings mit prohibitiv großen konstanten Faktoren, die sie unpraktisch machen. Diese Algorithmen erfüllen jedoch nicht die Kriterien für eine Klassifizierung in polynomieller Zeit, da ihre Ausführungszeit für das Zurückweisen von Instanzen nicht polynomiell begrenzt ist. Ein anschauliches Beispiel ist der folgende Algorithmus, der Levin zugeschrieben wird. Dieser Algorithmus akzeptiert korrekt die NP-vollständige Sprache SUBSET-SUM und arbeitet in polynomieller Zeit an Eingaben, die zu SUBSET-SUM gehören, genau dann, wenn P = NP:

// Algorithmus zur Annahme der NP-vollständigen Sprache SUBSET-SUM.
//
// Dieser Algorithmus arbeitet genau dann in polynomieller Zeit, wenn P = NP.
//
// „Polynomial-time“ impliziert, dass es innerhalb der polynomialen Zeit „Ja“ liefert, wenn
// die richtige Antwort ist „Ja“, und es wird auf unbestimmte Zeit ausgeführt, wenn die Antwort „Nein“ lautet.
//
// Eingabe: S, eine endliche Menge von ganzen Zahlen
// Ausgabe: „Ja“, wenn die Summe einer Teilmenge von S 0 ergibt.
// Andernfalls wird es auf unbestimmte Zeit ohne Ausgabe ausgeführt.
// Hinweis: „Programmnummer M“ bezieht sich auf das von abgeleitete Programm
// Konvertieren der Ganzzahl M in ihre binäre Darstellung, dann
// interpretiert diese Bitfolge als
// Programm. Alle möglichen Programme können sein
/ wird durch diese Methode generiert, obwohl die meisten keine Aktion ausführen
// aufgrund von Syntaxfehlern.
FÜR K = 1...∞
  FÜR M = 1...K
    Führen Sie Programm Nummer M für K Schritte mit Eingang S aus
    WENN das Programm eine Liste unterschiedlicher Ganzzahlen ausgibt
      UND die ganzen Zahlen sind alle in S
      UND die Summe der ganzen Zahlen ergibt 0
    DANN
      OUTPUT „ja“ und HALT

Dieser Algorithmus stellt ausschließlich dann einen polynomiellen Akzeptor für eine NP-vollständige Sprache dar, wenn P = NP. Der Begriff „Akzeptieren“ bedeutet, dass er innerhalb der Polynomzeit „Ja“-Antworten erzeugt, aber unbegrenzt laufen darf, wenn die Antwort „Nein“ lautet (eine Eigenschaft eines Halbalgorithmus).

Selbst unter der Annahme, dass P = NP, bleibt dieser Algorithmus zutiefst unpraktisch. Sollte das prägnanteste Programm, das SUBSET-SUM in Polynomzeit lösen kann, b Bits lang sein, würde der oben genannte Algorithmus mindestens 2^b − 1 andere Programme auswerten, bevor er darauf stößt.

Formale Definitionen

Komplexitätsklassen P und NP

Ein Entscheidungsproblem ist als Rechenproblem definiert, das eine Eingabezeichenfolge w aus einem Alphabet Σ akzeptiert und eine binäre Ausgabe erzeugt: „Ja“ oder „Nein“. Wenn ein Algorithmus (z. B. eine Turing-Maschine oder ein Computerprogramm mit unbegrenztem Speicher) die richtige Antwort für jede Eingabezeichenfolge der Länge n innerhalb von maximal cn^k Schritten generieren kann, wobei k und c von der spezifischen Eingabezeichenfolge unabhängige Konstanten sind, dann gilt das Problem als in Polynomialzeit lösbar und wird innerhalb der Klasse kategorisiert P. Formal stellt P die Sammlung von Sprachen dar, die von einer deterministischen Polynomzeit-Turingmaschine entschieden werden können.

Die Komplexitätsklasse P = { L : L = L ( M ) für eine deterministische Polynomialzeit-Turingmaschine M } {\displaystyle {\mathsf {P}}=\{L:L=L(M){\text{ für eine deterministische Polynomzeit-Turingmaschine }}M\}} definiert die Menge der Sprachen L, die durch eine Deterministik entschieden werden können Turingmaschine M, die innerhalb der Polynomzeit arbeitet.

wo

L ( M ) = { w ∈<!-- ∈ --> Σ<!-- Σ --> ∗<!-- ∗ --> : M akzeptiert w } {\displaystyle L(M)=\{w\in \Sigma ^{*}:M{\text{ akzeptiert }}w\}} bezeichnet die Sprache, die alle Zeichenfolgen w aus umfasst das Alphabet Σ ∗, die von der Turing-Maschine M.

Eine deterministische Polynomzeit-Turingmaschine ist definiert als eine deterministische Turingmaschine M, die die folgenden zwei Kriterien erfüllt:

1. Zuerst muss M für jede Eingabe w terminieren.
2. Zweitens muss eine positive Ganzzahl k ∈<!-- ∈ vorhanden sein --> N {\displaystyle k\in N} so dass die Zeitkomplexitätsfunktion T M ( n ) ∈<!-- ∈ --> O ( n k Es gilt:

   Die Funktion

   T M ( n ) = max { t M ( w ) : w ∈<!-- ∈ --> Σ<!-- Σ --> ∗<!-- ∗ --> , | w | = n } {\displaystyle T_M(n)=\max\{t_M(w):w\in \Sigma ^{*},|w|=n\}} stellt die maximale Anzahl von Schritten dar, die die Maschine M ausführt zum Anhalten für jede Eingabezeichenfolge w der Länge n.

   Außerdem wird $t_M(w)=Anzahl\; von\; SchritteMhält\; bei\; Eingabe\; anw.$

   {\displaystyle t_{M}(w)={\text{ Anzahl der Schritte }}M{\text{ benötigt, um bei Eingabe anzuhalten }}w. quantifiziert die Anzahl der Rechenschritte, die erforderlich sind, damit Maschine M anhält, wenn Eingabe w verarbeitet wird.

   Während die Komplexitätsklasse NP traditionell mithilfe nichtdeterministischer Turing-Maschinen definiert werden kann, verwenden moderne Methoden häufig die Konzepte eines Zertifikats und eines Verifizierers. Formal umfasst NP die Menge der Sprachen, die über ein endliches Alphabet und einen Verifizierer verfügen, der innerhalb polynomieller Zeit arbeitet. Der folgende Text beschreibt die Definition eines „Verifizierers“.

   Betrachten Sie L als eine Sprache, die über einem endlichen Alphabet, Σ, definiert ist.

   Eine Sprache L ist genau dann ein Element von NP, wenn eine binäre Beziehung R ⊂<!-- ⊂ --> Σ<!-- Σ --> ∗<!-- ∗ --> ×<!-- × --> Σ<!-- Σ --> ∗ <!-- ∗ --> {\displaystyle R\subset \Sigma ^{*}\times \Sigma ^{*}} und Es existiert eine positive ganze Zahl k, die die folgenden beiden Kriterien erfüllt:

   1. Die Bedingung dafür, dass ein Element x Mitglied der Sprache L ist, ist wie folgt definiert: for every x ∈<!-- ∈ --> Σ<!-- Σ --> ∗<!-- ∗ --> x ∈<!-- ∈ --> L ⇔<!-- ⇔ --> ∃<!-- ∃ --> y ∈<!-- ∈ --> Σ<!-- Σ --> ∗<!-- ∗ --> {\displaystyle x\in L\Leftrightarrow \exists y\in \Sigma ^{*}}, sodass das geordnete Paar (x, y) ein Element von R ist und die Länge von y, bezeichnet durch | y | , ist begrenzt durch O(| x ; und
   2. Außerdem ist die Sprache # y : ( x , y ) ∈<!-- ∈ --> R } {\displaystyle L_R=\{x\#y:(x,y)\in R\}}, konstruiert über das Alphabet Σ<!-- Σ --> ∪<!-- ∪ --> { #<!-- # --> } {\displaystyle \Sigma \cup \{\#\}}, muss von einer deterministischen Turing-Maschine innerhalb der Polynomzeit entscheidbar sein.

   Eine Turing-Maschine, die L_R entscheiden kann, wird als Verifizierer für die Sprache L bezeichnet. Dementsprechend wird ein Element y, das die Bedingung (x, y) ∈ R erfüllt, als Mitgliedschaftszertifikat für x innerhalb von L bezeichnet.

   Es ist wichtig zu beachten, dass nicht alle Verifizierer notwendigerweise auf Polynomialzeitbetrieb beschränkt sind. Damit eine Sprache L jedoch in die Komplexitätsklasse NP eingeordnet werden kann, ist die Existenz mindestens eines Verifizierers, der in polynomialer Zeit arbeitet, eine notwendige Bedingung.

   Anschauliches Beispiel

   Lass uns definieren:

   Die Menge 65§ } {\displaystyle \mathrm {COMPOSITE} =\left\{x\in \mathbb {N} \mid x=pq{\text{ für Ganzzahlen }}p,q>1\right\}} , umfasst alle natürlichen Zahlen x, die als Produkt zweier Ganzzahlen p und q ausgedrückt werden können, wobei sowohl p als auch q größer als 1 sind.

   Die Beziehung sei 42§ < y ≤ x  und  y  dividiert  x } . {\displaystyle R=\left\{(x,y)\in \mathbb {N} \times \mathbb {N} \mid 1 ist definiert als die Menge geordneter Paare (x, y) aus N × N, sodass y eine Ganzzahl größer als 1, aber kleiner oder gleich der Quadratwurzel von ist x und y ist ein Teiler von x.

   Die Feststellung, ob ein Wert x zusammengesetzt ist, ist gleichbedeutend mit der Feststellung, ob x zur Menge COMPOSITE gehört. Es kann nachgewiesen werden, dass die Menge COMPOSITE ein Mitglied von NP ist, indem bestätigt wird, dass sie der oben genannten Definition entspricht, vorausgesetzt, dass natürliche Zahlen binär dargestellt werden.

   Darüber hinaus wird COMPOSITE in P klassifiziert, einer Klassifizierung, die durch die Entwicklung des AKS-Primalitätstests erstellt wurde.

   NP-Vollständigkeit

   NP-Vollständigkeit kann durch mehrere äquivalente Formulierungen charakterisiert werden.

   Betrachten Sie L als eine Sprache, die über einem endlichen Alphabet Σ definiert ist.

   Eine Sprache L gilt genau dann als NP-vollständig, wenn sie die folgenden beiden Kriterien erfüllt:

   1. L ist ein Element von NP; und
   2. Jede Sprache L′ innerhalb von NP ist in polynomieller Zeit auf L reduzierbar, bezeichnet als L ′ ≤<!-- ≤ --> p L {\displaystyle L'\leq _{p}L}. Diese Reduzierbarkeit, L ′ ≤<!-- ≤ --> p L {\displaystyle L'\leq _{p}L} gilt genau dann, wenn die folgenden zwei Bedingungen erfüllt sind: Erstens existiert eine Funktion f: Σ* → Σ*, so dass für jedes w in Σ* die Äquivalenz ( w ∈<!-- ∈ --> L ′ ⇔<!-- ⇔ --> f ( w ) ∈<!-- ∈ --> L ) {\displaystyle (w\in L'\Leftrightarrow f(w)\in L)} ist wahr; und
   3. Zweitens existiert eine Polynomzeit-Turing-Maschine, die bei jeder Eingabe w mit f(w) auf ihrem Band anhält.

   Alternativ: Wenn L ein Element von NP ist und ein anderes NP-vollständiges Problem polynomiell auf L reduziert werden kann, dann ist L auch NP-vollständig. Diese Methode wird häufig verwendet, um die NP-Vollständigkeit neuer Probleme festzustellen.

   Vorgeschlagene Lösungen

   Obwohl das P-NP-Problem weitgehend ungelöst bleibt, haben zahlreiche Amateur- und einige professionelle Forscher Lösungen vorgeschlagen. Gerhard J. Wöginger dokumentierte zwischen 1986 und 2016 116 angebliche Beweise; Insbesondere behaupteten 61 P = NP, 49 behaupteten P ≠ NP und 6 präsentierten alternative Ergebnisse, beispielsweise dass das Problem unentscheidbar sei. Bestimmte Versuche, eine Lösung zwischen P und NP zu finden, erregten flüchtige Aufmerksamkeit in den Medien, doch diese Behauptungen wurden später widerlegt.

   Kulturelle Referenzen

   Der Film Travelling Salesman unter der Regie von Timothy Lanzone schildert die Erzählung von vier Mathematikern, die von der US-Regierung beauftragt wurden, das P-NP-Problem zu lösen.

   In „Treehouse of Horror VI“, der sechsten Episode der siebten Staffel von Die Simpsons', erscheint kurz die Gleichung P = NP, nachdem Homer versehentlich die „dritte“ betritt Dimension.“

   In der zweiten Episode der zweiten Staffel von Elementary mit dem Titel „Solve for X“ untersuchen Holmes und Watson die Morde an Mathematikern, die versuchten, P gegen NP zu lösen.

   Analoge Probleme

   • Das Problem R vs. RE ist analog, wobei R der Klasse P und RE der Klasse NP entspricht. Diese Klassen sind unterschiedlich, was durch die Existenz unentscheidbarer, aber überprüfbarer Probleme belegt wird, wie etwa Hilberts zehntes Problem, das RE-vollständig ist.
   • Innerhalb der Theorie der algebraischen Komplexität ist eine analoge Herausforderung das Problem VP vs. VNP. Ähnlich wie bei P vs. NP bleibt die Auflösung schwer zu bestimmen.
   • In der parametrisierten Komplexität stellt FPT vs. W[1] ein vergleichbares Problem dar.

   Exponentielle Zeithypothese

   • Exponentielle Zeithypothese
   • Liste ungelöster Probleme in der Informatik
   • Liste ungelöster Probleme in der Mathematik
   • Einzigartige Spiele-Vermutung

   Notizen

   Referenzen

   Quellen

   • Crowell, Rachel (28. Mai 2021). „Die größten ungelösten Fragen in der Mathematik bleiben größtenteils rätselhaft: Nur eines der sieben vor 21 Jahren benannten Millennium-Preis-Probleme wurde gelöst.“ . . Dieses Problem befasst sich mit der Frage, ob Fragen, die leicht überprüfbar sind (eine Klasse von Abfragen, die als NP bezeichnet werden), auch Lösungen haben, die leicht erkennbar sind (eine Klasse mit der Bezeichnung P).Hosch, William L. (11. August 2009). „P versus NP problem Mathematics.“ Encyclopædia Britannica. Abgerufen am 20. Juni, 2021."P-vs-NP-Problem." org (Cook, Levin). Archiviert vom Original am 18. Juni 2021. Abgerufen am 20. Juni, 2021. Stellen Sie sich ein Szenario vor, bei dem es um die Organisation von Wohnunterkünften für 400 Universitätsstudenten geht, wobei nur 100 Wohnheimplätze verfügbar sind. Um diese Aufgabe noch weiter zu erschweren, hat der Dekan eine Liste inkompatibler Studentenpaare bereitgestellt, mit der Auflage, dass solche Paare nicht in die endgültige Auswahl einbezogen werden sollten. Diese Situation veranschaulicht, was Informatiker als NP-Problem bezeichnen.Cormen, Thomas (2001). Einführung in Algorithmen. Cambridge, Massachusetts: MIT Press. ISBN 978-0-262-03293-3.
     • Cormen, Thomas (2001). Einführung in Algorithmen. Cambridge, Massachusetts: MIT Press ISBN 978-0-262-03293-3.Garey, Michael R. und Johnson, David S. (1979). Computer und Widerspenstigkeit: Ein Leitfaden zur Theorie der NP-Vollständigkeit. Reihe von Büchern in den Mathematischen Wissenschaften (1. Aufl.). New York: W. H. Freeman und Company. ISBN 9780716710455. MR 0519066. OCLC 247570676.Goldreich, Oded (2010). P, NP und NP-Vollständigkeit. Cambridge, England: Cambridge University Press.ISBN 978-0-521-12254-2.Immerman, Neil (1987). „Languages that Capture Complexity Classes". SIAM Journal on Computing, 16(4): 760–778. CiteSeerX 10.1.1.75.3035. doi:10.1137/0216051.Papadimitriou, Christos (1994). Rechenkomplexität. Boston, Massachusetts: Addison-Wesley. ISBN 978-0-201-53082-7.Fortnow, L. und Gasarch, W. „Computational complex.“
       • Fortnow, L.; Gasarch, W. „Rechenkomplexität“."P vs. NP und der Computational Complexity Zoo". 26. August 2014. Archiviert vom Original am 24. November 2021 – über YouTube.Quelle: TORIma Akademie Archive