NP-Vervollständigung

Das Boolesche Zufriedenheitsproblem (Sa) bittet darum zu bestimmen, ob a Aussageformel (Beispiel dargestellt) kann gemacht werden Stimmt durch eine angemessene Zuordnung von Wahrheitswerten zu seinen Variablen. Es ist zwar leicht zu überprüfen, ob eine bestimmte Zuordnung die Formel macht Stimmt,[1] Es ist keine im Wesentlichen schnellere Methode, um eine zufriedenstellende Zuordnung zu finden, als alle Aufgaben nacheinander zu versuchen. Kochen und Levin bewiesen, dass jedes leicht zu vergleichende Problem so schnell wie SAT gelöst werden kann, was daher NP-Complete ist.

Im Computerkomplexitätstheorieein Problem ist NP-Complete Wenn:

  1. Es ist ein Problem, für das die Richtigkeit jeder Lösung schnell verifiziert werden kann (nämlich in Polynomzeit) und ein Brute-Force-Suche Der Algorithmus kann eine Lösung finden, indem er alle möglichen Lösungen ausprobiert.
  2. Das Problem kann verwendet werden, um jedes andere Problem zu simulieren, für das wir schnell überprüft werden können, ob eine Lösung korrekt ist. In diesem Sinne sind NP-Complete-Probleme die schwierigsten Probleme, auf die Lösungen schnell überprüft werden können. Wenn wir Lösungen für ein NP-Complete-Problem schnell finden könnten, könnten wir schnell die Lösungen jedes anderen Problems finden, zu dem eine bestimmte Lösung leicht überprüft werden kann.

Der Name "NP-Complete" ist kurz für "nicht deterministische Polynomzeit-Zeit". In diesem Namen bezieht sich "nicht deterministisch" auf Nichtdeterministische Turing -Maschinen, eine Art, die Idee eines Brute-Force-Suchalgorithmus mathematisch zu formalisieren. Polynomzeit bezieht sich auf eine Zeitspanne, die für a als "schnell" angesehen wird deterministischer Algorithmus Überprüfen Sie eine einzelne Lösung oder für eine nichtdeterministische Turing -Maschine, um die gesamte Suche durchzuführen. "Vollständig"Bezieht sich auf das Eigentum, alles im selben simulieren zu können Komplexitätsklasse.

Genauer Polynomzeit),[2] so dass die Ausgabe für eine Eingabe "Ja" ist, wenn die Lösung nicht leer ist und "Nein" ist, wenn sie leer ist. Die Komplexitätsklasse von Problemen dieser Form wird genannt Npeine Abkürzung für "nicht deterministische Polynomzeit". Ein Problem soll sein Np-harte Wenn alles in NP in der Polynomzeit in sie transformiert werden kann, obwohl es möglicherweise nicht in NP ist. Umgekehrt ist ein Problem NP-Vervollständigung, wenn es sowohl in NP als auch in NP-Hard ist. Die NP-Complete-Probleme stellen die schwierigsten Probleme in NP dar. Wenn ein NP-Complete-Problem einen Polynomzeitalgorithmus aufweist, tun dies alle Probleme in NP. Der Satz von NP-Complete-Problemen wird häufig durch gekennzeichnet durch NP-C oder NPC.

Obwohl eine Lösung für ein NP-Complete-Problem sein kann verifiziert "schnell", es gibt keinen bekannten Weg dazu finden eine Lösung schnell. Das heißt, die Zeit, die erforderlich ist, um das Problem mit der derzeit bekannten Lösung zu lösen Algorithmus Erhöht sich schnell mit zunehmender Größe des Problems. Infolgedessen bestimmen Sie, ob es möglich ist, diese Probleme schnell zu lösen, genannt P gegen NP -Problem, ist eines der grundlegenden ungelöste Probleme in der Informatik heute.

Während eine Methode zur Berechnung der Lösungen für NP-Complete-Probleme schnell unentdeckt bleibt, Informatiker und Programmierer immer noch häufig auf NP-Complete-Probleme stoßen. NP-Complete-Probleme werden häufig durch die Verwendung behandelt Heuristik Methoden und Näherungsalgorithmen.

Überblick

NP-Complete-Probleme sind in Np, der Satz von allen Entscheidungsprobleme deren Lösungen können in der Polynomzeit überprüft werden; Np kann gleich definiert als die Reihe von Entscheidungsproblemen, die in der Polynomzeit auf a gelöst werden können Nichtdeterministische Turing-Maschine. Ein Problem p in NP ist NP-Complete, wenn jedes andere Problem in NP in transformiert (oder reduziert) werden kann p in Polynomzeit.

Es ist nicht bekannt, ob jedes Problem in NP schnell gelöst werden kann - dies wird als die genannt P gegen NP -Problem. Doch wenn Jedes NP-Complete-Problem kann dann schnell gelöst werden Jedes Problem in NP Kann, da die Definition eines NP-Completen-Problems besagt, dass jedes Problem in NP schnell auf jedes NP-Complete-Problem reduziert werden muss (dh in der Polynomzeit kann es reduziert werden). Aus diesem Grund wird oft gesagt, dass NP-Complete-Probleme sind Schwerer oder schwieriger als NP -Probleme im Allgemeinen.

Formale Definition

Siehe auch: Formale Definition für die NP-Vervollständigung (Artikel P = np)

Ein Entscheidungsproblem ist NP-Complete, wenn:

  1. ist in NP und
  2. Jedes Problem in NP ist reduzierbar zu in Polynomzeit.[3]

Es kann gezeigt werden, dass es in NP ist, indem er zeigt, dass eine Kandidatenlösung zu kann in Polynomzeit verifiziert werden.

Beachten Sie, dass ein Problem, das die Bedingung 2 erfüllt, sein soll Np-harte, ob es ihm den Zustand 1 erfüllt oder nicht.[4]

Eine Folge dieser Definition ist, dass, wenn wir einen Polynomzeitalgorithmus hatten (auf a UTM, oder irgend ein anderer Turing-äquivalent abstrakte Maschine) zum Wir könnten alle Probleme in NP in der Polynomzeit lösen.

Hintergrund

Euler -Diagramm zum P, Np, Np-complete und Np-harte Probleme. Die linke Seite ist unter der Annahme gültig, dass P ≠ npWährend die rechte Seite unter der Annahme gültig ist, dass P = NP (außer dass die leere Sprache und ihre Komplement niemals NP-Vervollständigung sind und im Allgemeinen nicht jedes Problem in P oder NP NP-Complete ist)

Das Konzept der NP-Vervollständigung wurde 1971 eingeführt (siehe Cook -Levin -Theorem), obwohl der Begriff NP-Complete wurde später eingeführt. Bei der 1971 Stoc Konferenz gab es eine heftige Debatte zwischen den Informatikern darüber, ob NP-Complete-Probleme in der Polynomzeit auf a gelöst werden konnten deterministisch Turing Maschine. John Hopcroft brachte alle auf der Konferenz zu einem Konsens darüber, ob die Frage, ob NP-Complete-Probleme in der Polynomzeit lösbar sind, zu einem späteren Zeitpunkt gestrichen werden sollte, da niemand formelle Beweise für ihre Ansprüche auf die eine oder andere Weise hatte. Dies ist als "die Frage, ob p = np" bezeichnet wird.

Niemand konnte noch schlüssig bestimmen, ob NP-Complete-Probleme in der Polynomzeit tatsächlich lösbar sind, was diese zu den großen macht ungelöste Probleme der Mathematik. Das Clay Mathematics Institute Bietet jedem, der einen formellen Beweis hat, eine Belohnung von 1 Million US -Dollar, die p = np oder p ≠ np hat.

Die Existenz von NP-Complete-Problemen ist nicht offensichtlich. Das Cook -Levin -Theorem stellt fest, dass die Boolesche Zufriedenheitsproblem ist NP-Complete, so dass solche Probleme existieren. 1972,, Richard Karp bewiesen, dass auch mehrere andere Probleme NP-Vervollständigung waren (siehe Karps 21 NP-Complete-Probleme); Daher gibt es eine Klasse von NP-Complete-Problemen (neben dem booleschen Erfüllbarkeitsproblem). Seit den ursprünglichen Ergebnissen wurde gezeigt, dass Tausende anderer Probleme durch Reduktionen anderer Probleme, die zuvor als NP-Complete gezeigt wurden, NP-Vervollständigung sind. Viele dieser Probleme werden in gesammelt Garey und Johnsons 1979 Buch Computer und Unverdaulichkeit: Ein Leitfaden zur Theorie der NP-Vervollständigung.[5]

NP-Complete-Probleme

Einige NP-Complete-Probleme, die die angeben Reduzierungen typischerweise verwendet, um ihre NP-Vervollständigung zu beweisen
Hauptartikel: Liste der NP-Complete-Probleme

Der einfachste Weg, um zu beweisen, dass ein neues Problem NP-Complete ist, besteht zuerst darin, zu beweisen, dass es in NP ist, und dann ein bekanntes NP-Complete-Problem zu reduzieren. Daher ist es nützlich, eine Vielzahl von NP-Complete-Problemen zu kennen. Die folgende Liste enthält einige bekannte Probleme, die NP-Vervollständigung sind, wenn sie als Entscheidungsprobleme ausgedrückt werden.

Rechts ist ein Diagramm einiger Probleme und die Reduzierungen Normalerweise verwendet, um ihre NP-Vervollständigung zu beweisen. In diesem Diagramm werden die Probleme von unten nach oben reduziert. Beachten Sie, dass dieses Diagramm als Beschreibung der mathematischen Beziehung zwischen diesen Problemen irreführend ist, da es a Polynomzeitreduktion zwischen zwei beliebigen Problemen mit NP; Es zeigt jedoch, wo das Nachweisen dieser Polynomzeitreduzierung am einfachsten war.

Es gibt oft nur einen kleinen Unterschied zwischen einem Problem in P und einem NP-Complete-Problem. Zum Beispiel die 3-Satsfabilität Das Problem, eine Beschränkung des booleschen Erfüllbarkeitsproblems, bleibt NP-Vervollständigung, während die etwas eingeschränkter 2-Satsfabilität Das Problem ist in P (insbesondere ist es NL-Complete), aber der etwas allgemeinere max. 2-sa. Das Problem ist wieder NP-Complete. Das Bestimmen, ob ein Diagramm mit 2 Farben gefärbt werden kann, ist in P, aber mit 3 Farben ist NP-Vervollständig Planare Graphen. Feststellen, ob eine Grafik a ist Kreislauf oder ist Bippartiziten ist sehr einfach (in L), aber ein maximaler zweipartnerer oder maximaler Zyklus-Subgraphen zu finden ist NP-Complete. Eine Lösung der Rucksackproblem Innerhalb eines festen Prozentsatzes der optimalen Lösung kann in der Polynomzeit berechnet werden, aber das Finden der optimalen Lösung ist NP-Complete.

Zwischenprobleme

Ein interessantes Beispiel ist das Graph Isomorphismus Problem, das Graphentheorie Problem der Bestimmung, ob a Graph Isomorphismus existiert zwischen zwei Grafiken. Zwei Grafiken sind isomorph Wenn man sein kann transformiert in den anderen einfach durch Umbenennen Eckpunkte. Betrachten Sie diese beiden Probleme:

  • Graph Isomorphismus: ist Graph G.1 isomorph zu Grafik g2?
  • Subgraph Isomorphismus: ist Grafik G.1 isomorph zu einem Untergraph der Grafik g2?

Das Problem der Subgraph-Isomorphismus ist NP-Complete. Es wird vermutet, dass das Graph-Isomorphismus-Problem weder in P noch in NP-Complete ist, obwohl es sich in NP befindet. Dies ist ein Beispiel für ein Problem, das angenommen wird schwer, wird aber nicht als NP-Vervollständigung angesehen. Diese Klasse heißt NP-Intermediate-Probleme und existiert nur dann, wenn p ≠ np.

Lösen von NP-Complete-Problemen

Gegenwärtig erfordern alle bekannten Algorithmen für NP-Complete-Probleme Zeit, dh zu Superpolynom in der Eingangsgröße in der Tat exponentiell in [klären] für einige Und es ist nicht bekannt, ob es schnellere Algorithmen gibt.

Die folgenden Techniken können angewendet werden, um Rechenprobleme im Allgemeinen zu lösen, und sie führen häufig zu erheblich schnelleren Algorithmen:

  • Annäherung: Anstatt nach einer optimalen Lösung zu suchen, suchen Sie nach einer Lösung, die höchstens ein Faktor von einer optimalen ist.
  • Randomisierung: Verwenden Sie Zufälligkeit, um einen schnelleren Durchschnitt zu erhalten Laufzeitund lassen Sie den Algorithmus mit einer geringen Wahrscheinlichkeit scheitern. Beachten Sie das Monte Carlo -Methode ist kein Beispiel für einen effizienten Algorithmus in diesem spezifischen Sinne, obwohl evolutionäre Ansätze wie wie Genetische Algorythmen vielleicht.
  • Einschränkung: Durch Einschränkung der Struktur der Eingabe (z. B. auf planare Graphen) sind normalerweise schnellere Algorithmen möglich.
  • Parametrisierung: Oft gibt es schnelle Algorithmen, wenn bestimmte Parameter der Eingabe festgelegt sind.
  • Heuristik: Ein Algorithmus, der in vielen Fällen "einigermaßen gut" funktioniert, aber für den es keinen Beweis gibt, dass es sowohl schnell ist als auch immer ein gutes Ergebnis erzielt. Metaheuristisch Ansätze werden häufig verwendet.

Ein Beispiel für einen heuristischen Algorithmus ist suboptimal Gieriger Malvorlagenalgorithmus benutzt für Grafikfarbe während der Zuteilung registrieren Phase einiger Compiler, eine Technik namens Graph-Coloring Global Register Allocation. Jeder Scheitelpunkt ist eine Variable, Kanten werden zwischen Variablen gezogen, die gleichzeitig verwendet werden, und die Farben geben das Register an, das jeder Variablen zugewiesen ist. Weil die meisten RISC Maschinen haben eine ziemlich große Anzahl allgemeiner Register, selbst ein heuristischer Ansatz ist für diese Anwendung wirksam.

Vollständigkeit unter verschiedenen Arten von Reduktion

In der oben angegebenen Definition von NP-Complete, dem Begriff die Ermäßigung wurde in der technischen Bedeutung einer Polynomzeit verwendet Viele Reduktion.

Eine andere Art von Reduktion ist die Polynomzeit-Turing-Reduktion. Ein Problem Ist Polynomzeit-Turing-reduzierbar auf ein Problem Wenn, bei einer Unterprogramme, die löst In der Polynomzeit könnte man ein Programm schreiben, das diese Unterroutine nennt und löst in Polynomzeit. Dies steht im Gegensatz zu vieler Reduzierbarkeit, was die Beschränkung hat, dass das Programm nur einmal den Unterprogramm aufrufen kann, und der Rückgabewert des Unterprogramms muss der Rückgabewert des Programms sein.

Wenn man das Analogon-zu-NP-Complete mit Turing-Reduktionen anstelle von vielen Reduktionen definiert, sind die resultierenden Probleme nicht kleiner als die NP-Complete. Es ist eine offene Frage, ob es größer wird.

Eine andere Art von Reduktion, die häufig auch zur Definition der NP-Vervollständigung verwendet wird, ist die logarithmischer Raum viele eins Reduktion Dies ist eine vielseitige Reduzierung, die nur mit einer logarithmischen Menge an Platz berechnet werden kann. Da jede Berechnung, die in der durchgeführten Berechnung durchgeführt werden kann logarithmischer Raum Kann auch in der Polynomzeit erfolgen, wenn es darum geht, dass es auch eine Polynom-Zeit-Reduktion gibt, wenn es einen logarithmischen Raum gibt. Diese Art der Reduktion ist raffinierter als die üblicheren Polynomzeit-viele Reduktionen und ermöglicht es uns, mehr Klassen wie z. P-Complete. Ob unter diesen Arten von Reduktionen die Definition von NP-Complete-Änderungen immer noch ein offenes Problem ist. Alle derzeit bekannten NP-Complete-Probleme sind unter NP-Vervollständigung unter Protokollraumreduzierungen. Alle derzeit bekannten NP-Complete-Probleme bleiben NP-Vervollständigung auch unter viel schwächeren Reduzierungen wie Reduzierungen und Reduzierungen. Einige NP-Complete-Probleme wie SAT sind bekanntermaßen auch unter polylogarithmischen Zeitprojektionen bezeichnet.[6] Es ist jedoch bekannt, dass das AC0 Reduktionen definieren eine streng kleinere Klasse als Polynomzeitverkleinerung.[7]

Benennung

Entsprechend Donald KnuthDer Name "NP-Complete" wurde populär von Alfred Aho, John Hopcroft und Jeffrey Ullman in ihrem berühmten Lehrbuch "Das Design und Analyse von Computeralgorithmen". Er berichtet, dass sie die Änderung in der eingeführt haben Galey -Proofs Für das Buch (aus "polynomial-komplett") gemäß den Ergebnissen einer Umfrage, die er von der durchgeführt hatte Theoretische Informatik Gemeinschaft.[8] Andere Vorschläge in der Umfrage[9] inbegriffen "Herkules"," beeindruckend ", Steiglitz's "hart gekocht" zu Ehren von Cook und Shen Lins Akronym "Pet", das für "wahrscheinlich exponentielle Zeit" stand, aber je nachdem, in welchem ​​Weg die P gegen NP -Problem ging, konnte für "nachweislich exponentielle Zeit" oder "zuvor exponentielle Zeit" stehen.[10]

Häufige Missverständnisse

Die folgenden Missverständnisse sind häufig.[11]

  • "NP-Complete-Probleme sind die schwierigsten bekannten Probleme." Da NP-Complete-Probleme in NP sind, ist ihre Laufzeit höchstens exponentiell. Es wurde jedoch nachweislich nachweislich, dass einige Probleme beispielsweise mehr Zeit benötigen Presburger -Arithmetik. Von einigen Problemen wurde sogar nachgewiesen, dass sie überhaupt nie gelöst werden können, zum Beispiel die Halting problem.
  • "NP-Complete-Probleme sind schwierig, da es so viele verschiedene Lösungen gibt." Einerseits gibt es viele Probleme, die einen so großen Lösungsraum haben, aber in Polynomzeit gelöst werden können (zum Beispiel Minimum Spanning Tree). Andererseits gibt es NP-Probleme mit höchstens eine Lösung, die unter randomisierter Polynomzeitreduktion NP-HART sind (siehe Valiant -Vazirani -Theorem).
  • "Die Lösung von NP-Complete-Problemen erfordert eine exponentielle Zeit." Erstens würde dies p ≠ np implizieren, was immer noch eine ungelöste Frage ist. Darüber hinaus haben einige NP-Complete-Probleme tatsächlich Algorithmen, die in superpolynomialer, aber subtexponentieller Zeit wie O (2) ausgeführt werden (2)√nn). Zum Beispiel die unabhängiger Satz und dominierender Satz Probleme für Planare Graphen sind NP-Complete, können aber in der subenexponentiellen Zeit mit dem gelöst werden Planar -Separator -Theorem.[12]
  • "Jede Instanz eines NP-Complete-Problems ist schwierig." Oft können einige Fälle oder sogar die meisten Fälle innerhalb der Polynomzeit leicht zu lösen sein. Sofern P = NP jedoch nicht, muss ein Polynom-Zeit-Algorithmus asymptotisch mehr als polynomisch viele der exponentiell viele Eingaben einer bestimmten Größe falsch sein.[13]
  • "Wenn p = np, können alle kryptografischen Chiffren gebrochen werden." Ein Polynomzeitproblem kann in der Praxis sehr schwer zu lösen sein, wenn der Grad oder die Konstanten des Polynoms groß genug sind. Zum Beispiel Chiffren mit einer festen Schlüssellänge, wie z. fortgeschrittener Verschlüsselungsstandard, kann alle in ständiger Zeit gebrochen werden, indem sie jeden Schlüssel ausprobieren (und daher bereits in P) ausprobieren, obwohl diese Zeit mit der aktuellen Technologie das Alter des Universums überschreiten kann. Zusätzlich, Informationstheoretische Sicherheit Bietet kryptografische Methoden, die auch bei unbegrenzter Rechenleistung nicht gebrochen werden können.

Eigenschaften

Betrachten a Entscheidungsproblem Als formale Sprache in einer festen Codierung ist der festgelegte NPC aller NP-Complete-Probleme nicht geschlossen unter:

Es ist nicht bekannt, ob NPC unter geschlossen ist Ergänzungda npc =Co-NPC wenn und nur wenn np =Co-NPund ob np = co-np ein ist offene Frage.[14]

Siehe auch

Verweise

Zitate

  1. ^ Zum Beispiel einfach zuweisen Stimmt Zu jeder Variablen macht die 18. Konjunktion (und damit die vollständige Formel) FALSCH.
  2. ^ Cobham, Alan (1965). "Die intrinsische rechnerische Schwierigkeit der Funktionen". Proc. Logik, Methodik und Philosophie der Wissenschaft II.. North Holland.
  3. ^ J. van Leeuwen (1998). Handbuch der theoretischen Informatik. Elsevier. p. 84. ISBN 978-0-262-72014-4.
  4. ^ J. van Leeuwen (1998). Handbuch der theoretischen Informatik. Elsevier. p. 80. ISBN 978-0-262-72014-4.
  5. ^ Garey, Michael R.; Johnson, D. S. (1979). Victor Klee (ed.). Computer und Unverdaulichkeit: Ein Leitfaden zur Theorie der NP-Vervollständigung. Eine Reihe von Büchern in den mathematischen Wissenschaften. San Francisco, Kalifornien: W. H. Freeman und Co. S.x+338. ISBN 978-0-7167-1045-5. HERR 0519066.
  6. ^ Agrawal, M.; Allender, e.; Rudich, Steven (1998). "Verringerung der Schaltungskomplexität: Ein Isomorphismus -Theorem und ein Gap -Theorem". Journal of Computer and System Sciences. 57 (2): 127–143. doi:10.1006/jcs.1998.1583. ISSN 1090-2724.
  7. ^ Agrawal, M.; Allender, e.; Impagliazzo, R.; Pitassi, T.; Rudich, Steven (2001). "Reduzierung der Komplexität der Reduktionen". Rechenkomplexität. 10 (2): 117–138. doi:10.1007/S00037-001-8191-1. ISSN 1016-3328. S2CID 29017219.
  8. ^ Don Knuth, Tracy Larrabee und Paul M. Roberts, Mathematisches Schreiben Archiviert 2010-08-27 bei der Wayback -Maschine § 25, MAA Notizen Nr. 14, Maa, 1989 (auch Stanford Technischer Bericht, 1987).
  9. ^ Knuth, D. F. (1974). "Ein terminologischer Vorschlag". Sigact News. 6 (1): 12–18. doi:10.1145/1811129.1811130. S2CID 45313676.
  10. ^ Siehe die Umfrage oder [1] Archiviert 2011-06-07 im Wayback -Maschine.
  11. ^ Ball, Philip. "DNA -Computer hilft reisenden Verkäufern". doi:10.1038/news000113-10.
  12. ^ Bern (1990); Deĭneko, Klinz & Woeginger (2006); Dorn et al. (2005); Lipton & Tarjan (1980).
  13. ^ Hemaspaandra, L. A.; Williams, R. (2012). "Sigact News -Komplexitätstheorie Spalte 76". ACM Sigact News. 43 (4): 70. doi:10.1145/2421119.2421135. S2CID 13367514.
  14. ^ Talbot, John; Welsh, D. J. A. (2006), Komplexität und Kryptographie: Eine Einführung, Cambridge University Press, p. 57, ISBN 9780521617710, Die Frage, ob NP und CO-NP gleich sind, ist wahrscheinlich das zweitwichtigste offene Problem in der Komplexitätstheorie nach der P-Versus-NP-Frage.

Quellen

Weitere Lektüre