Seznam NP-úplných problémů - List of NP-complete problems
Toto je seznam některých běžně známých problémů, které jsou NP-kompletní když je vyjádřeno jako rozhodovací problémy. Jelikož jsou známy stovky takových problémů, není tento seznam nijak komplexní. Mnoho problémů tohoto typu lze najít v Garey & Johnson (1979).
Grafy a hypergrafy
Grafy se často vyskytují v každodenních aplikacích. Mezi příklady patří biologické nebo sociální sítě, které v některých případech obsahují stovky, tisíce nebo dokonce miliardy uzlů (např. Facebook nebo LinkedIn ).
- 1-rovinnost[1]
- 3-dimenzionální shoda[2][3]
- Bipartitní rozměr[4]
- Kapacitní minimální kostra[5]
- Problém kontroly trasy (také zvaný Problém čínského pošťáka) pro smíšené grafy (s přímými i neorientovanými okraji). Program je řešitelný v polynomiálním čase, pokud má graf všechny neorientované nebo všechny směrované hrany. Varianty zahrnují problém venkovského pošťáka.[6]
- Clique problém[2][7]
- Kompletní zbarvení, aka achromatické číslo[8]
- Domatické číslo[9]
- Dominující sada, a.k.a. dominantní číslo[10]
- Mezi NP speciální případy patří hrana dominující sada problém, tj. dominující množinový problém v liniových grafech. NP-kompletní varianty zahrnují propojená dominující sada problém a maximální listový strom problém.[11]
- Problém se šířkou pásma[12]
- Problém s krytem Clique[2][13]
- Rank zbarvení a.k.a. pořadí cyklu
- Rozložený strom s omezeným stupněm[14]
- Přesné krytí problém. Zůstává NP-kompletní pro 3 sady. Řešení v polynomiálním čase pro 2 sady (to je a vhodný ).[2][15]
- Sada vrcholů zpětné vazby[2][16]
- Sada zpětné vazby[2][17]
- Homomorfismus grafů problém[18]
- Barvení grafu[2][19]
- Grafický oddíl do podgrafy konkrétních typů (trojúhelníky, izomorfní podgrafy, Hamiltonian podgrafy, lesy, perfektní shody ) jsou známé NP-úplné. Rozdělit na kliky je stejný problém jako zbarvení the doplněk daného grafu. Souvisejícím problémem je najít oddíl, který je optimální z hlediska počtu hran mezi částmi.[20]
- Hamiltonovské dokončení[21]
- Problém hamiltonovské cesty, řízené a neřízené.[2][22]
- Problém s nejdelší cestou[23]
- Maximální bipartitní podgraf nebo (zejména s váženými hranami) maximální řez.[2][24]
- Maximální nezávislá sada[25]
- Maximum Indukovaná cesta[26]
- Číslo průsečíku grafu[27]
- Metrická dimenze grafu[28]
- Minimální k-řez
- Steinerův strom nebo Minimální kostra pro podmnožinu vrcholů grafu.[2] (Minimální kostra pro celý graf je řešitelná v polynomiálním čase.)
- Maximalizace modularity[29]
- Šířka cesty[30]
- Nastavit kryt (také zvaný minimální krytí problém) Toto je ekvivalent transpozice matice dopadu k úderové sadě problému.[2][31]
- Nastavit rozdělení problém[32]
- Nejkratší celková délka cesty překlenující strom[33]
- Číslo svahu dvě zkoušky[34]
- Šířka stromu[30]
- Vrcholový kryt[2][35]
Matematické programování
- Problém se 3 oddíly[36]
- Problém s balením koše[37]
- Problém s batohem, kvadratický batoh a několik variant[2][38]
- Variace na Problém obchodního cestujícího. Problém grafů je NP-úplný, pokud jsou délky hran považovány za celá čísla. Problém bodů v rovině je NP-úplný s diskretizovanou euklidovskou metrikou a přímočarou metrikou. Je známo, že problém je NP (tvrdý) s (nediskretizovanou) euklidovskou metrikou.[39]
- Cestující obchodník s úzkým hrdlem[40]
- Programování celého čísla. Varianta, kde je požadováno, aby proměnné byly 0 nebo 1, se nazývá lineární programování nula jedna a několik dalších variant je také NP-kompletní[2][41]
- Latinské čtverce (Problém určení, zda lze částečně vyplněný čtverec vyplnit do jednoho)
- Numerická trojrozměrná shoda[42]
- Problém s oddílem[2][43]
- Problém kvadratického přiřazení[44]
- Řešení dvou proměnných kvadratických polynomů přes celá čísla.[45] Vzhledem k tomu, kladná celá čísla , najít kladná celá čísla takhle
- Kvadratické programování (NP-tvrdé v některých případech, P pokud je konvexní)
- Problém se součtem podmnožiny[46]
Formální jazyky a zpracování řetězců
- Nejbližší řetězec[47]
- Nejdelší běžný problém s posloupností ve více sekvencích[48]
- Ohraničená varianta Problém s korespondencí[49]
- Nejkratší společná supersequence[50]
- Problém s korekcí řetězce na řetězec[51]
Hry a hádanky
- Bitevní loď
- Býci a krávy, prodáváno jako Mistr mysli: určité problémy s optimalizací, ale ne samotná hra.
- Věčnost II
- (Zobecněný ) FreeCell[52]
- Fillomino[53]
- Hashiwokakero[54]
- Heyawake[55]
- (Zobecněný ) Okamžité šílenství[56]
- Kakuro (křížové částky)
- Kingdomino[57]
- Kuromasu (také známý jako Kurodoko)[58]
- LaserTank [59]
- Lemmings (s polynomiálním časovým limitem)[60]
- Rozsviť[61]
- Masyu[62]
- Problém konzistence hledání min[63] (ale viz Scott, Stege a van Rooij[64])
- Nimber (nebo Zelené číslo) směrovaného grafu.[65]
- Numberlink
- Nonogramy
- Nurikabe
- (Zobecněný ) Pandemický[66]
- Optimální řešení pro N×N×N Rubikova kostka[67]
- SameGame
- (Zobecněný ) Soubor[68]
- Slither Link na různých mřížkách[69][70][71]
- (Zobecněný ) Sudoku[69][72]
- Problémy související s Tetris[73]
- Verbální aritmetika
jiný
- Problém s alokací lůžka[74]
- Mezi
- Sestavení optimálního Bitcoin blok.[75]
- Booleovský problém uspokojivosti (SAT).[2][76] Existuje mnoho variant, které jsou také NP-kompletní. Důležitou variantou je situace, kdy má každá klauzule přesně tři literály (3SAT), protože se používá v důkazu mnoha dalších výsledků NP-úplnosti.[77]
- Spojovací booleovský dotaz[78]
- Cyklické objednávání
- Problém uspokojivosti obvodu
- Nekapacitovaný problém s umístěním zařízení
- Flow Scheduling Problem
- Zobecněný problém s přiřazením
- Vzestupná rovinnost testování[34]
- Problém nemocnic a obyvatel s páry
- Některé problémy související s Plánování pracovních míst
- Monochromatický trojúhelník[79]
- Minimální maximální nezávislá množina aka minimální nezávislá dominující sada[80]
- NP-kompletní speciální případy zahrnují minimální maximální shoda problém,[81] což se v zásadě rovná hrana dominující sada problém (viz výše).
- Maximální běžný problém izomorfismu podgrafu[82]
- Minimální rozloha stromu
- Minimální k-spanning tree
- Metrický K-střed
- Maximální uspokojivost 2[83]
- Modální logika S5 - Splnitelnost
- Některé problémy související s Víceprocesorové plánování
- Maximální hlasitost submatice - Problém výběru nejlépe podmíněné podmnožiny větší matice m x n. Tato třída problému je spojena s odhalením hodnosti QR faktorizace a D optimální experimentální návrh.[84]
- Minimální adiční řetězce pro sekvence.[85] Složitost řetězců minimálního přidání pro jednotlivá čísla není známa.[86]
- Nelineární univariační polynomy nad GF [2n], n délka vstupu. Opravdu, přes jakýkoli GF [qn].
- Plánování otevřeného obchodu
- Šířka cesty,[30] nebo ekvivalentně tloušťka intervalu, a číslo oddělení vrcholu[87]
- Třídění palačinek problém vzdálenosti pro řetězce[88]
- k-čínský pošťák
- Problém izomorfismu podgrafu[89]
- Variace Problém Steinerova stromu. Konkrétně s diskretizovanou euklidovskou metrikou, přímočarou metrikou. Je známo, že problém je NP (tvrdý) s (nediskretizovanou) euklidovskou metrikou.[90]
- Nastavit balení[2][91]
- Serializovatelnost historie databází[92]
- Plánování pro minimalizaci váženého času dokončení
- Řídká aproximace
- Řazení bloků[93] (Řazení podle blokových tahů)
- Druhá objednávka instance
- Šířka stromu[30]
- Testování, zda a strom mohou být reprezentovány jako Euklidovský minimální kostra
- Trojrozměrný Isingův model[94]
- Problém s směrováním vozidla
Viz také
- Existenciální teorie skutečností # Kompletní problémy
- Karpových 21 NP-úplných problémů
- Seznam problémů s PSPACE
- Redukce (složitost)
Poznámky
- ^ Grigoriev & Bodlaender (2007).
- ^ A b C d E F G h i j k l m n Ó p q Karp (1972)
- ^ Garey & Johnson (1979): SP1
- ^ Garey & Johnson (1979): GT18
- ^ Garey & Johnson (1979): ND5
- ^ Garey & Johnson (1979): ND25, ND27
- ^ Garey & Johnson (1979): GT19
- ^ Garey & Johnson (1979): GT5
- ^ Garey & Johnson (1979): GT3
- ^ Garey & Johnson (1979): GT2
- ^ Garey & Johnson (1979): ND2
- ^ Garey & Johnson (1979): GT40
- ^ Garey & Johnson (1979): GT17
- ^ Garey & Johnson (1979): ND1
- ^ Garey & Johnson (1979): SP2
- ^ Garey & Johnson (1979): GT7
- ^ Garey & Johnson (1979): GT8
- ^ Garey & Johnson (1979): GT52
- ^ Garey & Johnson (1979): GT4
- ^ Garey & Johnson (1979): GT11, GT12, GT13, GT14, GT15, GT16, ND14
- ^ Garey & Johnson (1979): GT34
- ^ Garey & Johnson (1979): GT37, GT38, GT39
- ^ Garey & Johnson (1979): ND29
- ^ Garey & Johnson (1979): GT25, ND16
- ^ Garey & Johnson (1979): GT20
- ^ Garey & Johnson (1979): GT23
- ^ Garey & Johnson (1979): GT59
- ^ Garey & Johnson (1979): GT61
- ^ Brandes, Ulrik; Delling, Daniel; Gaertler, Marco; Görke, Robert; Hoefer, Martin; Nikoloski, Zoran; Wagner, Dorothea (2006), Maximalizace modularity je těžké, arXiv:fyzika / 0608255, Bibcode:Fyzika 2006 ... 8255B
- ^ A b C d Arnborg, Corneil & Proskurowski (1987)
- ^ Garey & Johnson (1979): SP5, SP8
- ^ Garey & Johnson (1979): SP4
- ^ Garey & Johnson (1979): ND3
- ^ A b Garg, Ashim; Tamassia, Roberto (1995). "O výpočetní složitosti vzestupného a přímočarého testování rovinnosti". Přednášky z informatiky. 894/1995. 286–297. doi:10.1007/3-540-58950-3_384. ISBN 978-3-540-58950-1.
- ^ Garey & Johnson (1979): GT1
- ^ Garey & Johnson (1979): SP15
- ^ Garey & Johnson (1979): SR1
- ^ Garey & Johnson (1979): MP9
- ^ Garey & Johnson (1979): ND22, ND23
- ^ Garey & Johnson (1979): ND24
- ^ Garey & Johnson (1979): MP1
- ^ Garey & Johnson (1979): SP16
- ^ Garey & Johnson (1979): SP12
- ^ Garey & Johnson (1979): ND43
- ^ NP-úplné rozhodovací problémy pro kvadratické polynomy
- ^ Garey & Johnson (1979): SP13
- ^ Lanctot, J. Kevin; Li, Ming; Ma, Bin; Wang, Shaojiu; Zhang, Louxin (2003), „Rozlišování problémů s výběrem řetězců“, Informace a výpočet, 185 (1): 41–55, doi:10.1016 / S0890-5401 (03) 00057-9, PAN 1994748
- ^ Garey & Johnson (1979): SR10
- ^ Garey & Johnson (1979): SR11
- ^ Garey & Johnson (1979): SR8
- ^ Garey & Johnson (1979): SR20
- ^ Malte Helmert, Výsledky složitosti pro standardní srovnávací domény v plánování, Artificial Intelligence 143 (2): 219-262, 2003.
- ^ Yato, Takauki (2003). Složitost a úplnost hledání dalšího řešení a jeho aplikace na hádanky. CiteSeerX 10.1.1.103.8380.
- ^ „HASHIWOKAKERO JE NP-Complete“.
- ^ Holzer & Ruepp (2007)
- ^ Garey & Johnson (1979): GP15
- ^ Nguyen, Viet-Ha; Perrot, Kévin; Vallet, Mathieu (24. června 2020). „NP-úplnost hry KingdominoTM“. Teoretická informatika. 822: 23–35. doi:10.1016 / j.tcs.2020.04.007. ISSN 0304-3975.
- ^ Kölker, Jonas (2012). „Kurodoko je NP úplné“ (PDF). Journal of Information Processing. 20 (3): 694–706. doi:10.2197 / ipsjjip.20.694. S2CID 46486962.
- ^ Alexandersson, Per; Restadh, Petter (2020). "LaserTank je NP-Complete". Matematické aspekty počítačových a informačních věd. Přednášky z informatiky. Springer International Publishing. 11989: 333–338. arXiv:1908.05966. doi:10.1007/978-3-030-43120-4_26. ISBN 978-3-030-43119-8. S2CID 201058355.
- ^ Cormode, Graham (2004). Tvrdost hry Lumíci, nebo No, další důkazy o úplnosti NP (PDF).
- ^ Light Up je NP-Complete
- ^ Friedman, Erich (27. března 2012). „Pearl Puzzles are NP-complete“.
- ^ Kaye (2000)
- ^ Allan Scott, Ulrike Stege, Iris van Rooij, Hledání min nemusí být úplný NP, ale přesto je tvrdý, Matematický zpravodaj 33: 4 (2011), s. 5–17.
- ^ Garey & Johnson (1979): GT56
- ^ Nakai, Kenichiro; Takenaga, Yasuhiko (2012). „NP-úplnost pandemie“. Journal of Information Processing. 20 (3): 723–726. doi:10.2197 / ipsjjip.20.723. ISSN 1882-6652.
- ^ Demaine, Erik; Eisenstat, Sarah; Rudoy, Michail (2018). Optimální řešení Rubikovy kostky je NP-kompletní. 35. symposium o teoretických aspektech informatiky (STACS 2018). doi:10.4230 / LIPIcs.STACS.2018.24.
- ^ http://pbg.cs.illinois.edu/papers/set.pdf
- ^ A b Sato, Takayuki; Seta, Takahiro (1987). Složitost a úplnost hledání jiného řešení a jeho aplikace na hádanky (PDF). Mezinárodní symposium o algoritmech (SIGAL 1987).
- ^ Nukui; Uejima (březen 2007). „ASP - úplnost logiky Slither Link na několika sítích“. Poznámky Ipsj Sig. 2007 (23): 129–136.
- ^ Kölker, Jonas (2012). „Vybrané varianty sklouznutí odkazu jsou NP-kompletní“. Journal of Information Processing. 20 (3): 709–712. doi:10.2197 / ipsjjip.20.709.
- ^ PŘEHLED KOMPLEXNÍCH PLAZÁN NP, oddíl 23; Graham Kendall, Andrew Parkes, Kristian Spoerer; Březen 2008. (icga2008.pdf)
- ^ Demaine, Eric D .; Hohenberger, Susan; Liben-Nowell, David (25. – 28. Července 2003). Tetris je těžký, dokonce přibližně (PDF). Sborník z 9. mezinárodní konference v oblasti výpočetní techniky a kombinatoriky (COCOON 2003). Big Sky, Montana.
- ^ Lim, Andrew (1998), „Problém plánování kotviště“, Dopisy o operačním výzkumu, 22 (2–3): 105–110, doi:10.1016 / S0167-6377 (98) 00010-8, PAN 1653377
- ^ J. Bonneau, „těžba bitcoinů je NP-těžká
- ^ Garey & Johnson (1979): LO1
- ^ Garey & Johnson (1979): str. 48
- ^ Garey & Johnson (1979): SR31
- ^ Garey & Johnson (1979): GT6
- ^ Minimální nezávislá dominující sada
- ^ Garey & Johnson (1979): GT10
- ^ Garey & Johnson (1979): GT49
- ^ Garey & Johnson (1979): LO5
- ^ https://web.archive.org/web/20150203193923/http://www.meliksah.edu.tr/acivril/max-vol-original.pdf
- ^ Peter Downey, Benton Leong a Ravi Sethi. „Výpočetní sekvence s přídavnými řetězci“ SIAM J. Comput., 10 (3), 638–646, 1981
- ^ D. J. Bernstein, „Pippingerův umocňovací algoritmus (návrh)
- ^ Kashiwabara a Fujisawa (1979); Ohtsuki a kol. (1979); Lengauer (1981).
- ^ Hurkens, C .; Iersel, L. V .; Keijsper, J .; Kelk, S .; Stougie, L .; Tromp, J. (2007). Msgstr "Obrácení prefixů na binárních a ternárních řetězcích". SIAM J. Diskrétní matematika. 21 (3): 592–611. arXiv:matematika / 0602456. doi:10.1137/060664252.
- ^ Garey & Johnson (1979): GT48
- ^ Garey & Johnson (1979): ND13
- ^ Garey & Johnson (1979): SP3
- ^ Garey & Johnson (1979): SR33
- ^ Bein, W. W .; Larmore, L. L .; Latifi, S .; Sudborough, I.H. (1. ledna 2002). Třídění bloků je těžké. International Symposium on Parallel Architectures, Algorithms and Networks, 2002. I-SPAN '02. Řízení. 307–312. doi:10.1109 / ISPAN.2002.1004305. ISBN 978-0-7695-1579-3. S2CID 32222403.
- ^ Barry Arthur Cipra „The Ising Model Is NP-Complete“, SIAM News, sv. 33, č. 6.
Reference
Všeobecné
- Garey, Michael R.; Johnson, David S. (1979), Počítače a neodolatelnost: Průvodce po teorii NP-úplnosti, W. H. Freeman, ISBN 0-7167-1045-5. Tato kniha je klasická, rozvíjí teorii a poté katalogizuje mnoho NP-Complete problémy.
- Cook, S.A. (1971). "Složitost postupů prokazování věty". Proceedings, Third Annual ACM Symposium on the Theory of Computing, ACM, New York. str. 151–158. doi:10.1145/800157.805047.
- Karp, Richard M. (1972). "Redukovatelnost mezi kombinatorickými problémy". In Miller, Raymond E .; Thatcher, James W. (eds.). Složitost počítačových výpočtů. Plénum. str. 85–103.CS1 maint: ref = harv (odkaz)
- Dunne, P.E. "Komentovaný seznam vybraných NP-úplných problémů". COMP202, Ústav výpočetní techniky, University of Liverpool. Citováno 21. června 2008.
- Crescenzi, P .; Kann, V .; Halldórsson, M .; Karpinski, M.; Woeginger, G. „Kompendium problémů s optimalizací NP“. KTH NADA, Stockholm. Citováno 21. června 2008.
- Dahlke, K. "NP-úplné problémy". Matematický referenční projekt. Citováno 21. června 2008.
Specifické problémy
- Friedman, E (2002). „Perlové hádanky jsou NP-kompletní“. Stetson University, DeLand, Florida. Citováno 21. června 2008.
- Grigorjev, A; Bodlaender, H L (2007). Msgstr "Algoritmy pro grafy vložitelné s několika kříženími na hraně". Algorithmica. 49 (1): 1–11. CiteSeerX 10.1.1.61.3576. doi:10.1007 / s00453-007-0010-x. PAN 2344391. S2CID 8174422.CS1 maint: ref = harv (odkaz)
- Hartung, S; Nichterlein, A (2012). Jak svět počítá. Přednášky z informatiky. 7318. Springer, Berlín, Heidelberg. 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; Ruepp, Oliver (2007). „Problémy interiérového designu - analýza složitosti hry Heyawake“ (PDF). Sborník, 4. mezinárodní konference o zábavě s algoritmy, LNCS 4475. Springer, Berlín / Heidelberg. 198–212. doi:10.1007/978-3-540-72914-3_18. ISBN 978-3-540-72913-6.CS1 maint: ref = harv (odkaz)
- Kaye, Richard (2000). „Hledání min je NP-kompletní“. Matematický zpravodaj. 22 (2): 9–15. doi:10.1007 / BF03025367. S2CID 122435790.CS1 maint: ref = harv (odkaz) Další informace jsou k dispozici online na Stránky Hledání min Richarda Kayeho.
- Kashiwabara, T .; Fujisawa, T. (1979). "NP-úplnost problému nalezení grafu intervalu minimálního počtu klik obsahujícího daný graf jako podgraf". Řízení. Mezinárodní symposium o obvodech a systémech. 657–660.CS1 maint: ref = harv (odkaz)
- Ohtsuki, Tatsuo; Mori, Hajimu; Kuh, Ernest S .; Kashiwabara, Toshinobu; Fujisawa, Toshio (1979). "Přiřazení jednorozměrné logické brány a intervalové grafy". Transakce IEEE na obvodech a systémech. 26 (9): 675–684. doi:10.1109 / TCS.1979.1084695.CS1 maint: ref = harv (odkaz)
- Lengauer, Thomas (1981). "Černobílé oblázky a oddělení grafů". Acta Informatica. 16 (4): 465–475. doi:10.1007 / BF00264496. S2CID 19415148.CS1 maint: ref = harv (odkaz)
- Arnborg, Stefan; Corneil, Derek G.; Proskurowski, Andrzej (1987). „Složitost hledání vložení do a k-strom". SIAM Journal o algebraických a diskrétních metodách. 8 (2): 277–284. doi:10.1137/0608024.CS1 maint: ref = harv (odkaz)
- Cormode, Graham (2004). „Tvrdost hry Lumíci, nebo Ach ne, další důkazy o úplnosti NP“. Sborník ze třetí mezinárodní konference o zábavě s algoritmy (FUN 2004). str. 65–76.