Liste der NP-vollständigen Probleme - List of NP-complete problems

Dies ist eine Liste einiger der bekannteren Probleme, die NP-vollständig sind, wenn sie als Entscheidungsprobleme ausgedrückt werden . Da Hunderte solcher Probleme bekannt sind, erhebt diese Liste keinen Anspruch auf Vollständigkeit. Viele Probleme dieser Art sind bei Garey & Johnson (1979) zu finden .

Graphen und Hypergraphen

Graphen treten häufig in alltäglichen Anwendungen auf. Beispiele sind biologische oder soziale Netzwerke, die teilweise Hunderte, Tausende und sogar Milliarden von Knoten enthalten (zB Facebook oder LinkedIn ).

• 1-Planarität
• 3-dimensionaler Abgleich
• Zweiteilige Dimension
• Kapazitierter minimaler Spannbaum
• Routeninspektionsproblem (auch chinesisches Postbotenproblem genannt ) für gemischte Graphen (mit gerichteten und ungerichteten Kanten). Das Programm ist in polynomieller Zeit lösbar, wenn der Graph alle ungerichteten oder alle gerichteten Kanten hat. Varianten umfassen das ländliche Postbotenproblem.
• Cliquenproblem
• Vollständige Färbung , auch bekannt als achromatische Zahl
• Hausnummer
• Dominierendes Set , auch bekannt als Dominanznummer

Zu den NP-vollständigen Spezialfällen gehört das kantendominierende Mengenproblem, dh das dominierende Mengenproblem in Liniengraphen. NP-vollständige Varianten umfassen das Problem der verbundenen dominierenden Menge und das Problem des maximalen Blattspannbaums .

• Bandbreitenproblem
• Cliquen-Cover-Problem
• Rangfärbung, auch bekannt als Zyklusrang
• Gradabhängiger Spannbaum
• Genaues Abdeckungsproblem . Bleibt NP-vollständig für 3 Sätze. Lösbar in polynomieller Zeit für 2-Mengen (dies ist ein Matching ).
• Feedback-Scheitelpunktsatz
• Rückkopplungsbogen eingestellt
• Graph Homomorphismus Problem
• Diagrammfärbung
• Die Unterteilung von Graphen in Teilgraphen bestimmter Typen (Dreiecke, isomorphe Teilgraphen , Hamiltonsche Teilgraphen, Wälder , perfekte Matchings ) sind bekanntlich NP-vollständig. Die Aufteilung in Cliquen ist das gleiche Problem wie das Einfärben des Komplements des gegebenen Graphen. Ein verwandtes Problem besteht darin, eine Partition zu finden, die hinsichtlich der Anzahl von Kanten zwischen Teilen optimal ist.
• Hamiltonsche Vervollständigung
• Hamiltonsches Wegproblem , gerichtet und ungerichtet.
• Längstes Wegproblem
• Maximaler zweiteiliger Teilgraph oder (insbesondere bei gewichteten Kanten) maximaler Schnitt .
• Maximales unabhängiges Set
• Maximaler induzierter Pfad
• Schnittpunktnummer grafisch darstellen
• Metrische Dimension einer Grafik
• Minimaler k-Schnitt
• Steiner-Baum oder Minimaler Spannbaum für eine Teilmenge der Scheitelpunkte eines Graphen. (Der minimale Spannbaum für einen ganzen Graphen ist in polynomieller Zeit lösbar.)
• Maximierung der Modularität
• Pfadbreite
• Set-Cover (auch Minimum-Cover- Problem genannt) Dies entspricht durch Transponieren der Inzidenzmatrix dem Hitting-Set-Problem.
• Aufteilungsproblem einstellen
• Kürzeste Gesamtpfadlänge Spannbaum
• Prüfung der Steigung Nummer zwei
• Baumbreite
• Scheitelabdeckung

Mathematische Programmierung

• 3-Partitionsproblem
• Problem mit der Behälterverpackung
• Rucksackproblem , quadratisches Rucksackproblem und mehrere Varianten
• Variationen zum Problem des Handlungsreisenden . Das Problem für Graphen ist NP-vollständig, wenn die Kantenlängen ganzzahlig angenommen werden. Das Problem für Punkte auf der Ebene ist NP-vollständig mit der diskretisierten euklidischen Metrik und der geradlinigen Metrik. Das Problem ist bekanntlich NP-schwer mit der (nicht diskretisierten) euklidischen Metrik.
• Handelsreisender mit Engpass
• Integer-Programmierung . Die Variante, bei der Variablen 0 oder 1 sein müssen, wird als lineare Null-Eins-Programmierung bezeichnet, und einige andere Varianten sind ebenfalls NP-vollständig
• Lateinische Quadrate (Das Problem zu bestimmen, ob ein teilweise ausgefülltes Quadrat zu einem vervollständigt werden kann)
• Numerischer 3-dimensionaler Abgleich
• Partitionsproblem
• Quadratisches Zuordnungsproblem
• Lösen von quadratischen Polynomen mit zwei Variablen über die ganzen Zahlen. Gegeben positive ganze Zahlen finden Sie positive ganze Zahlen mit${\displaystyle \textstyle A,B,C\geq 0}$${\displaystyle x,y}$${\displaystyle Axe^{2}+By-C=0}$
• Quadratische Programmierung (NP-hart in einigen Fällen, P wenn konvex)
• Teilmengensummenproblem

Formale Sprachen und String-Verarbeitung

• Nächster String
• Längstes gemeinsames Teilsequenzproblem über mehrere Sequenzen
• Die beschränkte Variante des Post-Korrespondenzproblems
• Kürzeste gemeinsame Supersequenz
• Problem mit der Korrektur von String zu String

Spiele und Rätsel

• Tasche (Koralle)
• Schlachtschiff
• Bulls and Cows , vermarktet als Master Mind : gewisse Optimierungsprobleme, aber nicht das Spiel selbst.
• Ewigkeit II
• ( generalisiert ) FreeCell
• Fillomino
• Hashiwokakero
• Heyawake
• ( Verallgemeinert ) Sofortiger Wahnsinn
• Kakuro (Kreuzsummen)
• Königreichino
• Kuromasu (auch bekannt als Kurodoko)
• LaserTank
• Lemminge (mit polynomialer Zeitbegrenzung)
• Aufleuchten
• Masyu
• Minesweeper-Konsistenzproblem (aber siehe Scott, Stege & van Rooij)
• Nimber (oder Grundy-Zahl) eines gerichteten Graphen.
• Nummernlink
• Nonogramme
• Nurikabe
• ( generalisierte ) Pandemie
• Optimale Lösung für den N × N × N Zauberwürfel
• Gleiches Spiel
• ( verallgemeinert ) Set
• Slither Link auf verschiedenen Rastern
• ( verallgemeinert ) Sudoku
• Tentai-Show
• Probleme im Zusammenhang mit Tetris
• Verbale Arithmetik

Sonstiges

• Problem bei der Liegeplatzzuweisung
• Zwischenheit
• Zusammenstellen eines optimalen Bitcoin- Blocks.
• Boolesches Erfüllbarkeitsproblem (SAT). Es gibt viele Variationen, die auch NP-vollständig sind. Eine wichtige Variante ist, dass jede Klausel genau drei Literale hat (3SAT), da sie im Beweis vieler anderer NP-Vollständigkeitsergebnisse verwendet wird.
• Konjunktive Boolesche Abfrage
• Zyklische Bestellung
• Schaltungserfüllbarkeitsproblem
• Standortproblem ohne Kapazitäten
• Flow Shop-Planungsproblem
• Verallgemeinertes Zuordnungsproblem
• Nach oben Planarität Prüfung
• Finden der globalen Minimumlösung eines Hartree-Fock- Problems
• Probleme von Krankenhäusern und Bewohnern mit Paaren
• Einige Probleme im Zusammenhang mit der Job-Shop-Planung
• Monochromatisches Dreieck
• Minimaler maximaler unabhängiger Satz, auch bekannt als minimaler unabhängiger dominierender Satz

NP-vollständige Spezialfälle beinhalten das Minimum-Maximum-Matching- Problem, das im Wesentlichen gleich dem kantendominierenden Mengenproblem (siehe oben) ist.

• Problem des maximalen gemeinsamen Teilgraphen-Isomorphismus
• Mindestgradspannender Baum
• Minimaler k-aufspannender Baum
• Metrisches k-Zentrum
• Maximale 2-Erfüllbarkeit
• Modallogik S5-Erfüllbarkeit
• Einige Probleme im Zusammenhang mit der Mehrprozessorplanung
• Submatrix mit maximalem Volumen – Problem der Auswahl der am besten konditionierten Teilmenge einer größeren Matrix. Diese Klasse von Problemen ist mit Rank verbunden, der QR-Faktorisierungen und D optimales experimentelles Design aufdeckt .${\displaystyle m\times n}$
• Minimale Additionsketten für Sequenzen. Die Komplexität minimaler Additionsketten für einzelne Zahlen ist unbekannt.
• Nichtlineare univariate Polynome über GF[2 ⁿ ], n der Länge der Eingabe. Tatsächlich über jedem GF[q ⁿ ].
• Open-Shop-Planung
• Pfadbreite oder äquivalent Intervalldicke und Scheitelpunktabstandszahl
• Pancake-Sortierabstandsproblem für Saiten
• k-chinesischer Postbote
• Teilgraphen-Isomorphismusproblem
• Variationen des Steiner-Baum-Problems . Insbesondere mit der diskretisierten euklidischen Metrik, der geradlinigen Metrik. Das Problem ist bekanntlich NP-schwer mit der (nicht diskretisierten) euklidischen Metrik.
• Verpackung einstellen
• Serialisierbarkeit von Datenbankhistorien
• Planung zur Minimierung der gewichteten Fertigstellungszeit
• Spärliche Näherung
• Blocksortierung (Sortieren nach Blockbewegungen)
• Instanziierung zweiter Ordnung
• Baumbreite
• Testen, ob ein Baum als euklidischer minimaler Spannbaum dargestellt werden kann
• Dreidimensionales Ising-Modell
• Problem bei der Fahrzeugführung

Siehe auch

• Existenzielle Theorie der Realen#Vollständige Probleme
• Karps 21 NP-vollständige Probleme
• Liste der PSPACE-vollständigen Probleme
• Reduktion (Komplexität)

Anmerkungen

Verweise

Allgemein

• Garey, Michael R. ; Johnson, David S. (1979), Computer und Widerspenstigkeit: Ein Leitfaden zur Theorie der NP-Vollständigkeit , W. H. Freeman , ISBN 0-7167-1045-5. Dieses Buch ist ein Klassiker, der die Theorie entwickelt und dann viele NP-vollständige Probleme katalogisiert .
• Cook, SA (1971). „Die Komplexität der Theorem-Beweis-Verfahren“. Proceedings, Third Annual ACM Symposium on the Theory of Computing, ACM, New York . S. 151–158. doi : 10.1145/800157.805047 .
• Karp, Richard M. (1972). „Reduzierbarkeit zwischen kombinatorischen Problemen“. In Miller, Raymond E.; Thatcher, James W. (Hrsg.). Komplexität von Computerberechnungen . Plenum. S. 85–103.
• Dunne, PE "Eine kommentierte Liste ausgewählter NP-vollständiger Probleme" . COMP202, Dept. of Computer Science, University of Liverpool . Abgerufen am 21. Juni 2008 .
• Crescenzi, P.; Kann, V.; Halldorsson, M.; Karpinski, M. ; Wöginger, G . "Ein Kompendium von NP-Optimierungsproblemen" . KTH NADA, Stockholm . Abgerufen am 21. Juni 2008 .
• Dahlke, K. "NP-vollständige Probleme" . Mathe-Referenzprojekt . Abgerufen am 21. Juni 2008 .

Spezifische Probleme

• Friedmann, E (2002). "Perlenpuzzles sind NP-vollständig" . Stetson-Universität, DeLand, Florida . Abgerufen am 21. Juni 2008 .
• Grigorjew, A; Bodländer, HL (2007). "Algorithmen für einbettbare Graphen mit wenigen Kreuzungen pro Kante". Algorithmen . 49 (1): 1–11. CiteSeerX  10.1.1.61.3576 . doi : 10.1007/s00453-007-0010-x . MR  2.344.391 . S2CID  8174422 .
• Hartung, S; Nichterlein, A (2012). Wie die Welt rechnet . Skript zur Vorlesung Informatik. 7318 . Springer, Berlin, Heidelberg. S. 283–292. CiteSeerX  10.1.1.377.2077 . doi : 10.1007/978-3-642-30870-3_29 . ISBN 978-3-642-30869-7. S2CID  6112925 .
• Holzer, Markus; Rüpp, Oliver (2007). „Die Probleme der Innenarchitektur – Eine Komplexitätsanalyse des Spiels Heyawake“ (PDF) . Proceedings, 4th International Conference on Fun with Algorithms, LNCS 4475 . Springer, Berlin/Heidelberg. S. 198–212. doi : 10.1007/978-3-540-72914-3_18 . ISBN 978-3-540-72913-6.
• Kaye, Richard (2000). "Minesweeper ist NP-vollständig". Mathematischer Geheimdienst . 22 (2): 9–15. doi : 10.1007/BF03025367 . S2CID  122435790 .Weitere Informationen sind online auf den Minesweeper-Seiten von Richard Kaye verfügbar .
• Kashiwabara, T.; Fujisawa, T. (1979). „NP-Vollständigkeit des Problems, einen Graphen mit minimalem Cliquenzahlintervall zu finden, der einen gegebenen Graphen als Untergraphen enthält“. Verfahren . Internationales Symposium für Schaltkreise und Systeme . S. 657–660.
• Ohtsuki, Tatsuo; Mori, Hajimu; Kuh, Ernst S.; Kashiwabara, Toshinobu; Fujisawa, Toshio (1979). „Eindimensionale Logikgatterzuordnung und Intervallgraphen“. IEEE-Transaktionen zu Schaltkreisen und Systemen . 26 (9): 675–684. doi : 10.1109/TCS.1979.1084695 .
• Lengauer, Thomas (1981). „Schwarz-weiße Kieselsteine ​​und Graphentrennung“. Acta Informatica . 16 (4): 465–475. doi : 10.1007/BF00264496 . S2CID  19415148 .
• Arnborg, Stefan; Corneil, Derek G. ; Proskurowski, Andrzej (1987). „Komplexität der Suche nach Einbettungen in einem k- Baum“. SIAM Journal für algebraische und diskrete Methoden . 8 (2): 277–284. doi : 10.1137/0608024 .
• Cormode, Graham (2004). "Die Härte des Lemmings-Spiels, oder Oh nein, mehr NP-Vollständigkeitsbeweise". Proceedings of Third International Conference on Fun with Algorithms (FUN 2004) . S. 65–76.

Externe Links

• Ein Kompendium von NP-Optimierungsproblemen
• Graph von NP-vollständigen Problemen