P-gegen-NP-Problem - P versus 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 leicht zu lösen sein?

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

Der oben verwendete informelle Begriff schnell bedeutet die Existenz eines Algorithmus, der die Aufgabe löst, der in polynomieller Zeit ausgeführt wird , sodass die Zeit zum Erledigen der Aufgabe als Polynomfunktion von der Größe der Eingabe in den Algorithmus variiert (im Gegensatz zu sagen wir, exponentielle Zeit ). Die allgemeine Klasse von Fragen, für die ein Algorithmus eine Antwort in polynomieller Zeit liefern kann, ist " P " oder " Klasse P ". Bei einigen Fragen gibt es keine bekannte Möglichkeit, schnell eine Antwort zu finden, aber wenn man Informationen erhält, die die Antwort zeigen, ist es möglich, die Antwort schnell zu überprüfen. Die Klasse von Fragen, für die eine Antwort in polynomialer Zeit verifiziert werden kann, ist NP , was für "nondeterministic polynomial time" steht.

Eine Antwort auf die Frage P versus NP würde bestimmen, ob Probleme, die in polynomialer Zeit verifiziert werden können, auch in polynomialer Zeit gelöst werden können. Wenn sich herausstellt, dass P NP ist, was allgemein angenommen wird, würde dies bedeuten, dass es Probleme in NP gibt, die schwieriger zu berechnen als zu überprüfen sind: Sie könnten nicht in polynomieller Zeit gelöst werden, aber die Antwort könnte in polynomieller Zeit verifiziert werden .

Das Problem wird von vielen als das wichtigste offene Problem in der Informatik angesehen . Abgesehen davon, dass es ein wichtiges Problem in der Computertheorie ist , hätte ein Beweis in beiden Fällen tiefgreifende Auswirkungen auf Mathematik, Kryptographie , Algorithmenforschung, künstliche Intelligenz , Spieltheorie , Multimediaverarbeitung, Philosophie , Wirtschaft und viele andere Bereiche.

Es ist eines der sieben Millennium Prize Probleme, die vom Clay Mathematics Institute ausgewählt wurden und von denen jedes für die erste richtige Lösung mit 1.000.000 US-Dollar dotiert ist.

Beispiel

Betrachten Sie Sudoku , ein Spiel, bei dem der Spieler ein teilweise ausgefülltes Zahlenraster erhält und versucht, das Raster nach bestimmten Regeln zu vervollständigen. Gibt es bei einem unvollständigen Sudoku-Raster beliebiger Größe mindestens eine legale Lösung? Jede vorgeschlagene Lösung lässt sich leicht verifizieren, und die Zeit zum Überprüfen einer Lösung wächst langsam (polynomiell), wenn das Gitter größer wird. Alle bekannten Algorithmen zum Finden von Lösungen benötigen jedoch für schwierige Beispiele eine Zeit, die exponentiell wächst, wenn das Gitter größer wird. Sudoku ist also in NP (schnell überprüfbar), aber nicht in P (schnell auflösbar). Tausende anderer Probleme scheinen ähnlich zu sein, da sie schnell zu überprüfen, aber langsam zu lösen sind. Forscher haben gezeigt, dass viele der Probleme in NP die zusätzliche Eigenschaft haben, dass eine schnelle Lösung für jedes von ihnen verwendet werden kann, um eine schnelle Lösung für jedes andere Problem in NP zu erstellen, eine Eigenschaft namens NP-Vollständigkeit . Jahrzehntelanges Suchen hat für keines dieser Probleme eine schnelle Lösung gebracht, daher vermuten die meisten Wissenschaftler, dass keines dieser Probleme schnell gelöst werden kann. Dies wurde jedoch nie bewiesen.

Geschichte

Die genaue Aussage des P-versus-NP-Problems wurde 1971 von Stephen Cook in seinem wegweisenden Papier "The complex of theorem beweisverfahren" eingeführt (und unabhängig davon 1973 von Leonid Levin ).

Obwohl das P-gegen-NP-Problem 1971 formell definiert wurde, gab es frühere Hinweise auf die damit verbundenen Probleme, die Schwierigkeit des Beweises und die möglichen Konsequenzen. 1955 schrieb der Mathematiker John Nash einen Brief an die NSA , in dem er spekulierte, dass das Knacken eines ausreichend komplexen Codes eine exponentielle Zeitdauer in der Länge des Schlüssels erfordern würde. Falls bewiesen (und Nash war entsprechend skeptisch), würde dies implizieren, was jetzt P NP genannt wird, da ein vorgeschlagener Schlüssel leicht in polynomieller Zeit verifiziert werden kann. Eine weitere Erwähnung des zugrunde liegenden Problems erfolgte 1956 in einem Brief von Kurt Gödel an John von Neumann . Gödel fragte, ob das Beweisen von Theoremen (jetzt bekannt als co-NP-vollständig ) in quadratischer oder linearer Zeit gelöst werden könne , und wies auf eine der wichtigsten Konsequenzen hin – wenn ja, dann könnte die Entdeckung mathematischer Beweise automatisiert werden.

Kontext

Die Beziehung zwischen den Komplexitätsklassen P und NP wird in der Computational Complexity Theory untersucht , dem Teil der Berechnungstheorie, der sich mit den Ressourcen befasst, die während der Berechnung zur Lösung eines gegebenen Problems benötigt werden. Die häufigsten Ressourcen sind Zeit (wie viele Schritte zur Lösung eines Problems erforderlich sind) und Speicherplatz (wie viel Speicher zur Lösung eines Problems benötigt wird).

Bei einer solchen Analyse ist ein Modell des Computers erforderlich, für den die Zeit analysiert werden muss. Typischerweise gehen solche Modelle davon aus, dass der Computer deterministisch ist (angesichts des aktuellen Zustands des Computers und aller Eingaben gibt es nur eine mögliche Aktion, die der Computer ausführen kann ) und sequentiell (er führt Aktionen nacheinander aus).

In dieser Theorie besteht die Klasse P aus all den Entscheidungsproblemen ( unten definiert ), die auf einer deterministischen sequentiellen Maschine in einer polynomialen Zeitdauer der Eingabe gelöst werden können ; die Klasse NP besteht aus all jenen Entscheidungsproblemen, deren positive Lösungen bei richtiger Information in polynomieller Zeit verifiziert werden können, oder äquivalent deren Lösung in polynomieller Zeit auf einer nichtdeterministischen 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?

Zu dieser und ähnlichen Fragen hat William Gasarch seit 2002 drei Forscherbefragungen durchgeführt. Das Vertrauen, dass P NP zugenommen hat – im Jahr 2019 glaubten 88 % an P NP, gegenüber 83 % im Jahr 2012 und 61 % im Jahr 2002. Beschränkt man sich auf Experten, waren die Antworten im Jahr 2019 zu 99 % der Meinung, dass P NP ist. Diese Umfragen sagen nichts darüber aus, ob P=NP wahr ist, wie Gasarch selbst feststellte: ″Dies bringt uns der Lösung von P=?NP oder dem Wissen, wann es gelöst wird, nicht näher, aber es versucht, ein Ziel zu sein Bericht über die subjektive Meinung dieser Zeit.″

NP-Vollständigkeit

Euler-Diagramm für P , NP , NP-vollständige und NP-schwere Menge von Problemen (ohne die leere Sprache und ihr Komplement, die zu P gehören, aber nicht NP-vollständig sind)

Um die P = NP-Frage anzugehen, 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 noch in polynomieller Zeit verifiziert werden kann. Das heißt, jedes NP-Problem kann in jedes der NP-vollständigen Probleme transformiert werden. Informell ist ein NP-vollständiges Problem ein NP-Problem, das mindestens so "schwer" ist wie jedes andere Problem in NP.

NP-schwere Probleme sind mindestens so schwierig wie NP-Probleme; dh alle NP-Probleme können (in polynomieller Zeit) auf sie reduziert werden. NP-schwere Probleme müssen nicht in NP liegen; dh sie müssen keine in polynomieller Zeit verifizierbaren Lösungen haben.

Zum Beispiel ist das Boolesche Erfüllbarkeitsproblem nach dem Cook-Levin-Theorem NP-vollständig , sodass jede Instanz eines beliebigen Problems in NP mechanisch in eine Instanz des Booleschen Erfüllbarkeitsproblems in polynomieller Zeit umgewandelt werden kann. Das Boolesche Erfüllbarkeitsproblem ist eines von vielen solchen NP-vollständigen Problemen. Wenn ein NP-vollständiges Problem in P liegt, dann folgt P = NP. Es wurde jedoch gezeigt, dass viele wichtige Probleme NP-vollständig sind, und für keines davon ist ein schneller Algorithmus bekannt.

Allein aufgrund der Definition ist nicht ersichtlich, dass es NP-vollständige Probleme gibt; ein triviales und erfundenes NP-vollständiges Problem kann jedoch wie folgt formuliert werden: Gibt es bei einer Beschreibung einer Turingmaschine M, die garantiert in polynomieller Zeit anhält, eine Eingabe polynomialer Größe, die M akzeptiert? Es ist in NP, weil es (bei einer gegebenen Eingabe) einfach zu überprüfen ist, ob M die Eingabe akzeptiert, indem man M simuliert ; es ist NP-vollständig, weil der Verifizierer für jede bestimmte Instanz eines Problems in NP als Polynomialzeitmaschine M codiert werden kann , die die zu verifizierende Lösung als Eingabe verwendet. Dann wird die Frage, ob die Instanz eine Ja- oder Nein-Instanz ist, dadurch bestimmt, ob eine gültige Eingabe vorhanden ist.

Das erste natürliche Problem, das sich als NP-vollständig erwiesen hat, war das Boolesche Erfüllbarkeitsproblem, auch bekannt als SAT. Wie oben erwähnt, ist dies das Cook-Levin-Theorem; sein Beweis, dass die Erfüllbarkeit NP-vollständig ist, enthält technische Details über Turing-Maschinen in Bezug auf die Definition von NP. Nachdem jedoch bewiesen wurde, dass dieses Problem NP-vollständig ist, bietet der Beweis durch Reduktion eine einfachere Möglichkeit zu zeigen, dass viele andere Probleme ebenfalls NP-vollständig sind, einschließlich des oben diskutierten Spiels Sudoku. In diesem Fall zeigt der Beweis, dass eine Lösung von Sudoku in polynomieller Zeit auch verwendet werden könnte, um lateinische Quadrate in polynomieller Zeit zu vervollständigen . Dies wiederum liefert eine Lösung für das Problem der Partitionierung von dreiteiligen Graphen in Dreiecke, die dann verwendet werden könnte, um Lösungen für den als 3-SAT bekannten Spezialfall von SAT zu finden, der dann eine Lösung für die allgemeine Boolesche Erfüllbarkeit liefert. Eine polynomiale Zeitlösung für Sudoku führt also durch eine Reihe mechanischer Transformationen zu einer polynomialen Zeitlösung der Erfüllbarkeit, die wiederum verwendet werden kann, um jedes andere NP-Problem in polynomieller Zeit zu lösen. Durch solche Transformationen ist eine riesige Klasse von scheinbar nicht zusammenhängenden Problemen alle aufeinander reduzierbar und in gewisser Weise "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 polynomielle Laufzeit definiert ist, ist die Klasse EXPTIME die Menge aller Entscheidungsprobleme mit exponentieller Laufzeit. Mit anderen Worten, jedes Problem in EXPTIME ist durch eine deterministische Turingmaschine in O (2 p ( n ) ) Zeit lösbar , wobei p ( n ) eine Polynomfunktion von n ist . Ein Entscheidungsproblem ist EXPTIME-vollständig, wenn es in EXPTIME liegt, und jedes Problem in EXPTIME hat eine Polynomialzeit-Viele-Eins-Reduktion . Es ist bekannt, dass eine Reihe von Problemen EXPTIME-vollständig sind. Da gezeigt werden kann, dass P EXPTIME ist, liegen diese Probleme außerhalb von P und benötigen daher mehr als polynomiale Zeit. Tatsächlich können sie nach dem Zeithierarchiesatz nicht in wesentlich kürzerer als exponentieller Zeit gelöst werden. Beispiele sind das Finden einer perfekten Strategie für Schachstellungen auf einem N × N- Brett und ähnliche Probleme für andere Brettspiele.

Noch mehr Zeit erfordert das Problem, den Wahrheitsgehalt einer Aussage in der Presburger Arithmetik zu entscheiden. Fischer und Rabin haben 1974 bewiesen, dass jeder Algorithmus, der über die Wahrheit von Presburger-Aussagen der Länge n entscheidet, eine Laufzeit von mindestens einer Konstanten c hat . Daher ist bekannt, dass das Problem mehr als eine exponentielle Laufzeit benötigt. Noch schwieriger sind die unentscheidbaren Probleme wie das Halteproblem . Sie können von keinem Algorithmus vollständig gelöst werden, in dem Sinne, dass es für einen bestimmten Algorithmus mindestens eine Eingabe gibt, für die dieser Algorithmus nicht die richtige Antwort liefert; es wird entweder die falsche Antwort produzieren, ohne eine schlüssige Antwort enden oder auf andere Weise ewig laufen, ohne überhaupt eine Antwort zu produzieren.

Es können auch andere Fragen als Entscheidungsprobleme betrachtet werden. Eine solche Klasse, bestehend aus Zählproblemen, heißt #P : 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 schwer sein wie das entsprechende NP-Problem, da eine Anzahl von Lösungen sofort sagt, ob mindestens eine Lösung existiert, wenn die Anzahl größer als Null ist. Überraschenderweise entsprechen einige #P-Probleme, von denen angenommen wird, dass sie schwierig sind, einfachen (zum Beispiel linearen Zeit-)P-Problemen. Für diese Probleme ist es sehr einfach zu sagen, ob es Lösungen gibt, aber es ist sehr schwer zu sagen, wie viele. Viele dieser Probleme sind #P-vollständig und gehören daher zu den schwierigsten Problemen in #P, da eine polynomiale Zeitlösung für jedes von ihnen eine polynomiale Zeitlösung für alle anderen #P- Probleme ermöglichen würde.

Probleme in NP, von denen nicht bekannt ist, dass sie in P oder NP-vollständig sind

1975 zeigte Richard E. Ladner , dass für P NP Probleme in NP existieren, die weder in P noch NP-vollständig sind. Solche Probleme werden als NP-Zwischenprobleme bezeichnet. Das Graphisomorphismusproblem , das diskrete Logarithmusproblem und das ganzzahlige Faktorisierungsproblem sind Beispiele für Probleme, von denen angenommen wird, dass sie NP-intermediär sind. Sie sind einige der wenigen NP-Probleme, von denen nicht bekannt ist, dass sie in P liegen oder NP-vollständig sind.

Das Graphisomorphie Problem ist das rechnerische Problem der Bestimmung , ob zwei endliche Graphen sind isomorph . Ein wichtiges ungelöstes Problem in der Komplexitätstheorie ist, ob das Graphisomorphismusproblem in P, NP-vollständig oder NP-intermediär ist. Die Antwort ist nicht bekannt, aber es wird angenommen, dass das Problem zumindest nicht NP-vollständig ist. Wenn der Isomorphismus des Graphen NP-vollständig ist, kollabiert die polynomielle Zeithierarchie auf ihre zweite Ebene. Da allgemein angenommen wird, dass die Polynomhierarchie nicht auf eine endliche Ebene kollabiert, wird angenommen, dass Graphisomorphismus nicht NP-vollständig ist. Der beste Algorithmus für dieses Problem läuft nach László Babai in quasi-polynomialer Zeit .

Das ganzzahlige Faktorisierungsproblem ist das Rechenproblem der Bestimmung der Primfaktorzerlegung einer gegebenen ganzen Zahl. Als Entscheidungsproblem formuliert, ist es das Problem der Entscheidung, ob die Eingabe einen Faktor kleiner als k hat . Es ist kein effizienter ganzzahliger Faktorisierungsalgorithmus bekannt, und diese Tatsache bildet die Grundlage mehrerer moderner kryptographischer Systeme, wie beispielsweise des RSA- Algorithmus. Das ganzzahlige Faktorisierungsproblem liegt in NP und in co-NP (und sogar in UP und co-UP). Wenn das Problem NP-vollständig ist, kollabiert die polynomiale Zeithierarchie auf ihre erste Ebene (dh NP = co-NP). Der bekannteste Algorithmus zur ganzzahligen Faktorisierung ist das allgemeine Zahlenfeldsieb , das die erwartete Zeit benötigt

um eine n- Bit-Ganzzahl zu faktorisieren. Der bekannteste Quantenalgorithmus für dieses Problem, der Shor-Algorithmus , läuft jedoch in polynomieller Zeit, obwohl dies nicht anzeigt, wo das Problem in Bezug auf Nicht- Quantenkomplexitätsklassen liegt .

Bedeutet P "einfach"?

Die Grafik zeigt die Laufzeit vs. Problemgröße für ein Rucksackproblem eines hochmodernen, spezialisierten Algorithmus. Die quadratische Anpassung legt nahe, dass die algorithmische Komplexität des Problems O((log( n )) 2 ).

Bei der gesamten obigen Diskussion wurde davon ausgegangen, dass P "leicht" bedeutet und "nicht in P" "schwierig" bedeutet, eine Annahme, die als Cobhams These bekannt ist . Dies ist eine übliche und einigermaßen genaue Annahme in der Komplexitätstheorie; es hat jedoch einige Vorbehalte.

Erstens ist es in der Praxis nicht immer richtig. Ein theoretischer Polynomalgorithmus kann extrem große konstante Faktoren oder Exponenten haben, was ihn unpraktisch macht. Zum Beispiel kann das Problem der Entscheidung , ob ein Graph G enthält H als minor , wo H festgelegt ist, kann in einer Laufzeit von gelöst wird O ( n 2 ), wobei n die Anzahl der Knoten in G . Die große O-Notation verbirgt jedoch eine Konstante, die superexponentiell von H abhängt . Die Konstante ist größer als (unter Verwendung der Aufwärtspfeil-Notation von Knuth ) und wobei h die Anzahl der Scheitelpunkte in H ist .

Andererseits kann es auch dann, wenn gezeigt wird, dass ein Problem NP-vollständig ist und selbst wenn P NP ist, noch effektive Ansätze zur Lösung des Problems in der Praxis geben. Es gibt Algorithmen für viele NP-vollständige Probleme, wie das Rucksackproblem , das Travelling-Salesman-Problem und das Boolesche Erfüllbarkeitsproblem , die viele reale Instanzen in angemessener Zeit optimal lösen können. Die empirische Durchschnitts-Case-Komplexität (Zeit vs. Problemgröße) solcher Algorithmen kann überraschend gering sein. Ein Beispiel ist der Simplex-Algorithmus in der linearen Programmierung , der in der Praxis überraschend gut funktioniert; trotz exponentieller Worst-Case- Zeitkomplexität läuft es auf Augenhöhe mit den bekanntesten Polynomialzeitalgorithmen.

Schließlich gibt es Berechnungsarten, die nicht dem Turing-Maschinenmodell entsprechen, auf dem P und NP definiert sind, wie Quantenberechnung und randomisierte Algorithmen .

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

Cook liefert eine Neuformulierung des Problems im P-VERSUS-NP-PROBLEM als: Ist P = NP ? . Umfragen zufolge glauben die meisten Informatiker, dass P NP ist. Ein Hauptgrund für diese Annahme ist, dass nach jahrzehntelanger Untersuchung dieser Probleme niemand in der Lage war, einen Polynomialzeitalgorithmus für eines der mehr als 3000 wichtigen bekannten NP-vollständigen Probleme zu finden (siehe Liste der NP-vollständigen Probleme ). Diese Algorithmen wurden gesucht, lange bevor das Konzept der NP-Vollständigkeit überhaupt definiert wurde ( die 21 NP-vollständigen Probleme von Karp , unter den ersten gefundenen Problemen , waren alle bekannte existierende Probleme zu dem Zeitpunkt, als sie als NP-vollständig erwiesen wurden). Darüber hinaus würde das Ergebnis P = NP viele andere verblüffende Ergebnisse implizieren, von denen derzeit angenommen wird, dass sie falsch sind, wie beispielsweise NP = co-NP und P = PH .

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

Wenn P = NP, dann wäre die Welt ein grundlegend anderer Ort, als wir normalerweise annehmen. "Kreative Sprünge" würden keinen besonderen Wert haben, keine grundlegende Lücke zwischen der Lösung eines Problems und dem Erkennen der Lösung, sobald sie gefunden wurde.

Auf der anderen Seite glauben einige Forscher, dass es zu viel Selbstvertrauen gibt, P NP zu glauben, und dass Forscher auch Beweise für P = NP untersuchen sollten. Im Jahr 2002 wurden beispielsweise diese Aussagen gemacht:

Das Hauptargument für P ≠ NP ist das völlige Fehlen grundlegender Fortschritte auf dem Gebiet der erschöpfenden 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 tiefe Theorien gelöst werden können.

An Spekulationen zu hängen 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 widersprach, obwohl sie alle erforderlichen Methoden entwickelt hatten.

Konsequenzen der Lösung

Einer der Gründe, warum das Problem so viel Aufmerksamkeit auf sich zieht, sind die Konsequenzen einiger möglicher Antworten. Beide Lösungsrichtungen würden die Theorie enorm voranbringen und vielleicht auch enorme praktische Konsequenzen haben.

P = NP

Ein Beweis, dass P = NP ist, könnte erstaunliche praktische Konsequenzen haben, wenn der Beweis zu effizienten Methoden zur Lösung einiger der wichtigen Probleme in NP führt. Die möglichen Konsequenzen, sowohl positive als auch negative, ergeben sich, da verschiedene NP-vollständige Probleme in vielen Bereichen von grundlegender Bedeutung sind.

Es ist auch sehr gut möglich, dass ein Beweis nicht zu praktikablen Algorithmen für NP-vollständige Probleme führt. Die Formulierung des Problems erfordert nicht, dass das Begrenzungspolynom klein oder sogar spezifisch bekannt ist. Ein nicht-konstruktiver Beweis könnte zeigen, dass eine Lösung existiert, ohne einen Algorithmus oder eine bestimmte Schranke anzugeben. Selbst wenn der Beweis konstruktiv ist und ein explizites Begrenzungspolynom und algorithmische Details zeigt, ist der Algorithmus in der Praxis möglicherweise nicht effizient genug, wenn das Polynom nicht sehr niedrig ist. In diesem Fall wäre der erste Beweis hauptsächlich für Theoretiker von Interesse, aber die Erkenntnis, dass polynomiale Zeitlösungen möglich sind, würde sicherlich die Forschung nach besseren (und möglicherweise praktikablen) Methoden antreiben, um diese zu erreichen.

Ein Beispiel für ein Feld, das durch eine Lösung mit P = NP entwurzelt werden könnte, ist die Kryptographie , die darauf beruht, dass bestimmte Probleme schwierig sind. Eine konstruktive und effiziente Lösung für ein NP-vollständiges Problem wie 3-SAT würde die meisten existierenden Kryptosysteme zerstören, einschließlich:

  • Vorhandene Implementierungen der Public-Key-Kryptografie , eine Grundlage für viele moderne Sicherheitsanwendungen wie sichere Finanztransaktionen über das Internet.
  • Symmetrische Chiffren wie AES oder 3DES , die zur Verschlüsselung von Kommunikationsdaten verwendet werden.
  • Cryptographic Hash , die zugrunde liegt blockchain cryptocurrencies wie Bitcoin und wird zum Authentifizieren Software - Updates verwendet. Für diese Anwendungen muss das Problem, ein Vorabbild zu finden, das auf einen bestimmten Wert hasht, schwierig sein, um nützlich zu sein, und sollte idealerweise exponentielle Zeit erfordern. Wenn jedoch P = NP ist, kann das Auffinden 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 von Natur aus auf P-NP-Unäquivalenz basieren.

Auf der anderen Seite gibt es enorme positive Konsequenzen, die sich daraus ergeben würden, viele derzeit mathematisch unlösbare Probleme handhabbar zu machen. Zum Beispiel sind viele Probleme im Operations Research NP-vollständig, wie zum Beispiel einige Arten von Integer-Programmierung und das Travelling-Salesman-Problem . Effiziente Lösungen für diese Probleme hätten enorme Auswirkungen auf die Logistik. Viele andere wichtige Probleme, wie einige Probleme bei der Vorhersage der Proteinstruktur , sind ebenfalls NP-vollständig; wären diese Probleme effizient lösbar, könnte dies erhebliche Fortschritte in den Biowissenschaften und der Biotechnologie bewirken.

Aber solche Veränderungen können im Vergleich zu der Revolution, die eine effiziente Methode zur Lösung NP-vollständiger Probleme in der Mathematik selbst bewirken würde, an Bedeutung verlieren. Gödel stellte in seinen frühen Gedanken zur Rechenkomplexität fest, dass eine mechanische Methode, die jedes Problem lösen könnte, die Mathematik revolutionieren würde:

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

Ähnlich sagt Stephen Cook (wobei nicht nur ein Beweis, sondern ein praktisch effizienter Algorithmus angenommen wird)

... es würde die Mathematik transformieren, indem es einem Computer erlaubt, einen formalen Beweis für jeden Satz zu finden, der einen Beweis von angemessener Länge hat, da formale Beweise leicht in polynomieller Zeit erkannt werden können. Beispielprobleme können durchaus alle CMI - Preisprobleme umfassen .

Forschungsmathematiker verbringen ihre Karriere damit, Theoreme zu beweisen, und einige Beweise haben Jahrzehnte oder sogar Jahrhunderte gebraucht, um sie zu finden, nachdem Probleme formuliert wurden – zum Beispiel brauchte Fermats letzter Satz mehr als drei Jahrhunderte, um sie zu beweisen. Eine Methode, die garantiert Beweise für Theoreme findet, sollte es eine "angemessene" 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, aber bezüglich der Auswirkungen eines möglichen Beweises zurückhaltend ist:

[...] wenn Sie sich eine endliche, aber unglaublich große Zahl M vorstellen – wie zum Beispiel die Zahl 10↑↑↑↑3, die ich in meinem Artikel über "Bewältigung mit der Endlichkeit" besprochen habe –, dann gibt es eine riesige Anzahl möglicher Algorithmen, die n M bitweise oder Additions- oder Verschiebeoperationen an n gegebenen Bits, und es ist wirklich schwer zu glauben, dass all diese Algorithmen versagen. Mein Hauptpunkt ist jedoch, dass ich nicht glaube, dass die Gleichung P = NP selbst dann hilfreich sein wird, wenn sie bewiesen ist, da ein solcher Beweis fast sicher nichtkonstruktiv sein wird.

Schematische Darstellung der Komplexitätsklassen vorausgesetzt , dass P   NP. Die Existenz von Problemen innerhalb von NP aber außerhalb von P und NP-vollständig wurde unter dieser Annahme durch den Satz von Ladner nachgewiesen .

P ≠ NP

Ein Beweis, der zeigte, dass P ≠ NP die praktischen rechnerischen Vorteile eines Beweises für P = NP verfehlen würde, aber dennoch einen sehr bedeutenden Fortschritt in der Theorie der rechnerischen Komplexität darstellen würde und eine Anleitung für zukünftige Forschungen bieten würde. Es würde es ermöglichen, formal zu zeigen, dass viele häufige Probleme nicht effizient gelöst werden können, sodass 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 Fokussierung der Forschung bereits stattgefunden.

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

Ergebnisse zur Beweisschwierigkeit

Obwohl das P = NP-Problem selbst trotz eines Millionenpreises und einer großen Menge an engagierter Forschung offen bleibt, haben Bemühungen zur Lösung des Problems zu mehreren neuen Techniken geführt. Insbesondere zeigten einige der fruchtbarsten Forschungen im Zusammenhang mit dem P = NP-Problem, dass bestehende Beweistechniken nicht leistungsfähig genug sind, um die Frage zu beantworten, was darauf hindeutet, dass neue technische Ansätze erforderlich sind.

Als zusätzlicher Beweis für die Schwierigkeit des Problems fallen im Wesentlichen alle bekannten Beweistechniken der Computational Complexity Theory in eine der folgenden Klassifikationen, von denen jede als unzureichend bekannt ist, um zu beweisen, dass P NP:

Einstufung Definition
Relativierung von Beweisen Stellen Sie sich eine Welt vor, in der jeder Algorithmus Abfragen an eine feste Unterroutine namens Orakel stellen darf (eine Blackbox, die einen festen Satz von Fragen in konstanter Zeit beantworten kann, z. , und die Laufzeit des Orakels wird nicht auf die Laufzeit des Algorithmus angerechnet. Die meisten Beweise (insbesondere die klassischen) gelten einheitlich in einer Welt mit Orakeln, unabhängig davon, was das Orakel tut. Diese Beweise werden als relativieren bezeichnet . 1975 zeigten Baker, Gill und Solovay , dass P = NP in Bezug auf einige Orakel ist, während P NP für andere Orakel ist. Da relativierende Beweise nur Aussagen beweisen können, die bezüglich aller 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 die unteren Schranken der Schaltungskomplexität, die als natürliche Beweise bezeichnet werden . Zu dieser Zeit waren alle bisher bekannten unteren Schranken von Schaltungen natürlich, und die Schaltungskomplexität wurde als ein sehr vielversprechender Ansatz zur Auflösung von P = NP angesehen. Razborov und Rudich haben jedoch gezeigt, dass, wenn Einwegfunktionen existieren, keine natürliche Beweismethode zwischen P und NP unterscheiden kann. Obwohl die Existenz von Einwegfunktionen nie formal bewiesen wurde, glauben die meisten Mathematiker, dass dies der Fall ist, und ein Beweis für ihre Existenz wäre eine viel stärkere Aussage als P NP. Daher ist es unwahrscheinlich, dass natürliche Beweise allein P = NP lösen können.
Algebrisierende Beweise Nach dem Baker-Gill-Solovay-Ergebnis wurden neue nicht-relativierende Beweistechniken erfolgreich verwendet, um zu beweisen, dass IP = PSPACE . Im Jahr 2008 zeigten Scott Aaronson und Avi Wigderson jedoch , dass das wichtigste technische Werkzeug, das beim IP = PSPACE-Beweis verwendet wird, die sogenannte Arithmetisierung , ebenfalls nicht ausreicht, um P = NP aufzulösen.

Diese Barrieren sind ein weiterer Grund, warum NP-vollständige Probleme nützlich sind: Wenn ein Polynomialzeitalgorithmus für ein NP-vollständiges Problem demonstriert werden kann, würde dies das P = NP-Problem auf eine Weise lösen, die durch die obigen Ergebnisse nicht ausgeschlossen wird.

Diese Barrieren haben auch einige Informatiker zu der Annahme veranlasst, dass das P-gegen-NP-Problem möglicherweise unabhängig von Standard-Axiomensystemen wie ZFC ist (kann in ihnen nicht bewiesen oder widerlegt werden). Die Interpretation eines Unabhängigkeitsergebnisses könnte sein, dass entweder kein Polynomialzeitalgorithmus für NP-vollständige Probleme existiert und ein solcher Beweis nicht in (zB) ZFC konstruiert werden kann, oder dass Polynomialzeitalgorithmen für NP-vollständige Probleme existieren können, aber es ist unmöglich, in ZFC zu beweisen, dass solche Algorithmen richtig sind. Wenn jedoch mit Techniken der derzeit als anwendbar bekannten Art gezeigt werden kann, dass das Problem auch mit viel schwächeren Annahmen, die die Peano-Axiome (PA) für die ganzzahlige Arithmetik erweitern, nicht entschieden werden kann, dann gäbe es notwendigerweise fast- Polynomialzeitalgorithmen für jedes Problem in NP. Wenn man (wie die meisten Komplexitätstheoretiker) glaubt, dass nicht alle Probleme in NP effiziente Algorithmen haben, folgt daraus, dass ein Unabhängigkeitsbeweis mit diesen Techniken nicht möglich ist. Darüber hinaus impliziert dieses Ergebnis, dass der Nachweis der Unabhängigkeit von PA oder ZFC mit derzeit bekannten Techniken nicht einfacher ist, als die Existenz effizienter Algorithmen für alle Probleme in NP zu beweisen.

Behauptete Lösungen

Während das P-gegen-NP-Problem im Allgemeinen als ungelöst gilt, haben viele Amateur- und einige professionelle Forscher Lösungen gefordert. Gerhard J. Woeginger führt eine Liste, die ab 2016 62 angebliche Beweise für P = NP, 50 Beweise für P NP, 2 Beweise für das Problem nicht beweisbar und einen Beweis für die Unentscheidbarkeit enthält. Offensichtlich sind mindestens 53 dieser Beweise falsch. Einige Versuche, P gegen NP aufzulösen, haben kurze Medienaufmerksamkeit erhalten, obwohl diese Versuche inzwischen widerlegt wurden.

Logische Charakterisierungen

Das P = NP-Problem kann in Form von ausdrückbaren bestimmten Klassen logischer Aussagen als Ergebnis der Arbeit in deskriptiver Komplexität neu formuliert werden .

Betrachten Sie alle Sprachen endlicher Strukturen mit einer festen Signatur einschließlich einer linearen Ordnungsbeziehung . Dann können alle diese Sprachen in P in Logik erster Ordnung unter Hinzufügung eines geeigneten Kleinste- Festkomma-Kombinators ausgedrückt werden . Effektiv ermöglicht dies in Kombination mit der Reihenfolge die Definition rekursiver Funktionen. Solange die Signatur neben der Distinguished Order Relation mindestens ein Prädikat oder eine Funktion enthält, so dass der Platzbedarf für die Speicherung solcher endlicher Strukturen tatsächlich polynomiell in der Anzahl der Elemente in der Struktur ist, charakterisiert dies P genau.

In ähnlicher Weise ist NP die Menge von Sprachen, die in der existenziellen Logik zweiter Ordnung ausdrückbar sind – das heißt, der Logik zweiter Ordnung, die darauf beschränkt ist, eine universelle Quantifizierung über Beziehungen, Funktionen und Teilmengen auszuschließen . Die Sprachen in der Polynom - Hierarchie , PH , entsprechen alle zweiter Ordnung Logik. Somit kann die Frage "Ist P eine echte Teilmenge von NP" umformuliert werden als "Ist die existenzielle Logik zweiter Ordnung in der Lage, Sprachen (von endlichen linear geordneten Strukturen mit nichttrivialer Signatur) zu beschreiben, die Logik erster Ordnung mit dem kleinsten Fixpunkt nicht kann?" . Das Wort "existentiell" kann sogar aus der vorherigen Charakterisierung gestrichen werden, da P = NP genau dann, wenn P = PH ist (da die erstere begründen würde, dass NP = co-NP, was wiederum NP = PH impliziert).

Polynomialzeitalgorithmen

Es ist kein Algorithmus für ein NP-vollständiges Problem bekannt, der in polynomieller Zeit abläuft. Es gibt jedoch Algorithmen für NP-vollständige Probleme mit der Eigenschaft, dass, wenn P = NP, der Algorithmus in polynomieller Zeit läuft, wenn Instanzen akzeptiert werden (allerdings mit enormen Konstanten, was den Algorithmus unpraktisch macht). Diese Algorithmen qualifizieren sich jedoch nicht als polynomielle Zeit, da ihre Laufzeit beim Zurückweisen von Instanzen nicht polynomiell ist. Der folgende Algorithmus von Levin (ohne Zitat) ist ein solches Beispiel unten. Es akzeptiert korrekt die NP-vollständige Sprache SUBSET-SUM . Es läuft in polynomieller Zeit an Eingängen, die in SUBSET-SUM sind, genau dann, wenn P = NP:

// Algorithm that accepts the NP-complete language SUBSET-SUM.
//
// this is a polynomial-time algorithm if and only if P = NP.
//
// "Polynomial-time" means it returns "yes" in polynomial time when
// the answer should be "yes", and runs forever when it is "no".
//
// Input: S = a finite set of integers
// Output: "yes" if any subset of S adds up to 0.
// Runs forever with no output otherwise.
// Note: "Program number M" is the program obtained by
// writing the integer M in binary, then
// considering that string of bits to be a
// program. Every possible program can be
// generated this way, though most do nothing
// because of syntax errors.
FOR K = 1...∞
  FOR M = 1...K
    Run program number M for K steps with input S
    IF the program outputs a list of distinct integers
      AND the integers are all in S
      AND the integers sum to 0
    THEN
      OUTPUT "yes" and HALT

Wenn, und nur wenn P = NP, dann ist dies ein Polynomialzeitalgorithmus, der eine NP-vollständige Sprache akzeptiert. "Akzeptieren" bedeutet, dass es in polynomieller Zeit "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. Wenn das kürzeste Programm, das SUBSET-SUM in polynomieller Zeit lösen kann, b Bits lang ist, versucht der obige Algorithmus zuerst mindestens 2 b − 1 andere Programme.

Formale Definitionen

P und NP

Konzeptionell ist ein Entscheidungsproblem ein Problem, das als Eingabe eine Zeichenkette w über einem Alphabet annimmt und "ja" oder "nein" ausgibt. Wenn es einen Algorithmus (z. B. eine Turingmaschine oder ein Computerprogramm mit unbegrenztem Speicher) gibt, der die richtige Antwort für jede Eingabezeichenfolge der Länge n in höchstens cn k Schritten liefern kann , wobei k und c Konstanten sind, die von der Eingabezeichenfolge unabhängig sind , dann sagen wir, dass das Problem in polynomieller Zeit lösbar ist und ordnen es der Klasse P zu. Formal ist P definiert als die Menge aller Sprachen, die durch eine deterministische polynomiale Turingmaschine entschieden werden können. Das ist,

wo

und eine deterministische Turingmaschine mit polynomialer Zeit ist eine deterministische Turingmaschine M , die die folgenden zwei Bedingungen erfüllt:

  1. M hält an allen Eingängen w und
  2. es gibt so dass , wobei O sich auf die große O-Notation bezieht und

NP kann auf ähnliche Weise mit nichtdeterministischen Turing-Maschinen (dem traditionellen Weg) definiert werden. Ein moderner Ansatz zur Definition von NP besteht jedoch darin, das Konzept von Zertifikat und Verifizierer zu verwenden . Formal ist NP als die Menge von Sprachen über einem endlichen Alphabet definiert, die einen Verifizierer haben, der in polynomieller Zeit läuft, wobei der Begriff des "Verifizierers" wie folgt definiert ist.

Sei L eine Sprache über einem endlichen Alphabet, .

L ∈ NP genau dann, wenn es eine binäre Beziehung und eine positive ganze Zahl k gibt, so dass die folgenden beiden Bedingungen erfüllt sind:

  1. Für alle , so dass ( x , y ) R und ; und
  2. die Sprache über ist durch eine deterministische Turingmaschine in polynomieller Zeit entscheidbar.

Ein Turing Maschine , die entscheidet , L R ist ein sogenannter Verifizierer für L und a y , so dass ( x , y ) ∈ R ist ein sogenanntes Zertifikat Mitgliedschaft von x in L .

Im Allgemeinen muss ein Verifizierer nicht polynomial sein. Damit L jedoch in NP ist, muss es einen Verifizierer geben, der in polynomieller Zeit läuft.

Beispiel

Lassen

Offensichtlich ist die Frage, ob ein gegebenes x ist ein Verbund entspricht der Frage, ob x ist Teil des Komposits. Es kann gezeigt werden, dass COMPOSITE ∈ NP, indem man verifiziert, dass es die obige Definition erfüllt (wenn wir natürliche Zahlen mit ihren binären Darstellungen identifizieren).

COMPOSITE ist zufällig auch in P, eine Tatsache, die durch die Erfindung des AKS-Primalitätstests gezeigt wurde .

NP-Vollständigkeit

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

Sei L eine Sprache über einem endlichen Alphabet Σ.

L ist genau dann NP-vollständig, wenn die folgenden beiden Bedingungen erfüllt sind:

  1. L NP; und
  2. jedes L in NP ist polynomial-zeitreduzierbar auf L (geschrieben als ), wobei genau dann die folgenden beiden Bedingungen erfüllt sind:
    1. Es existiert f  : Σ* → Σ* so dass für alle w in Σ* gilt: ; und
    2. es existiert eine Polynomialzeit-Turingmaschine, die mit f ( w ) auf ihrem Band bei jeder Eingabe w anhält .

Wenn alternativ L ∈ NP ist und es ein weiteres NP-vollständiges Problem gibt, das polynomiell auf L reduziert werden kann , dann ist L NP-vollständig. Dies ist eine übliche Methode, um zu beweisen, dass ein neues Problem NP-vollständig ist.

Popkultur

Der Film Travelling Salesman von Regisseur Timothy Lanzone ist die Geschichte von vier Mathematikern, die von der US-Regierung angeheuert wurden, um das P-gegen-NP-Problem zu lösen.

In der sechsten Episode der Simpson ' siebten Staffel ‚ Treehouse of Horror VI ‘, die Gleichung P = NP ist kurz nach Homer zufällig stolpert in die ‚dritte Dimension‘ zu sehen.

In der zweiten Episode der 2. Staffel von Elementary , „Löst für X“ dreht sich um Sherlock und Watson die Morde an Mathematiker untersuchen , die P - versus - NP zu lösen versuchen.

Siehe auch

Anmerkungen

Verweise

Quellen

Weiterlesen

Externe Links