Jump to content

List of NP-complete problems

From Wikipedia, the free encyclopedia

This is a list of some of the more commonly known problems that are NP-complete when expressed as decision problems. As there are thousands of such problems known, this list is in no way comprehensive. Many problems of this type can be found in Garey & Johnson (1979).

Graphs and hypergraphs

[edit]

Graphs occur frequently in everyday applications. Examples include biological or social networks, which contain hundreds, thousands and even billions of nodes in some cases (e.g. Facebook or LinkedIn).

NP-complete special cases include the edge dominating set problem, i.e., the dominating set problem in line graphs. NP-complete variants include the connected dominating set problem and the maximum leaf spanning tree problem.[3]: ND2 
NP-complete special cases include the minimum maximal matching problem,[3]: GT10  which is essentially equal to the edge dominating set problem (see above).

Mathematical programming

[edit]

Formal languages and string processing

[edit]

Games and puzzles

[edit]

Other

[edit]

See also

[edit]

Notes

[edit]
  1. ^ Grigoriev & Bodlaender (2007).
  2. ^ a b c d e f g h i j k l m n o p q Karp (1972)
  3. ^ a b c d e f g h i j k l m n o p q r s t u v w x y z aa ab ac ad ae af ag ah ai aj ak al am an ao ap aq ar as at au av aw ax ay az ba bb bc bd be Garey & Johnson (1979)
  4. ^ Minimum Independent Dominating Set
  5. ^ Brandes, Ulrik; Delling, Daniel; Gaertler, Marco; Görke, Robert; Hoefer, Martin; Nikoloski, Zoran; Wagner, Dorothea (2006), Maximizing Modularity is hard, arXiv:physics/0608255, Bibcode:2006physics...8255B
  6. ^ a b Arnborg, Corneil & Proskurowski (1987)
  7. ^ Kashiwabara & Fujisawa (1979); Ohtsuki et al. (1979); Lengauer (1981).
  8. ^ a b Garg, Ashim; Tamassia, Roberto (1995). "On the computational complexity of upward and rectilinear planarity testing". Lecture Notes in Computer Science. Vol. 894/1995. pp. 286–297. doi:10.1007/3-540-58950-3_384. ISBN 978-3-540-58950-1.
  9. ^ Schaefer, Marcus; Sedgwick, Eric; Štefankovič, Daniel (September 2003). "Recognizing string graphs in NP". Journal of Computer and System Sciences. 67 (2): 365–380. doi:10.1016/S0022-0000(03)00045-X.
  10. ^ Lanctot, J. Kevin; Li, Ming; Ma, Bin; Wang, Shaojiu; Zhang, Louxin (2003), "Distinguishing string selection problems", Information and Computation, 185 (1): 41–55, doi:10.1016/S0890-5401(03)00057-9, MR 1994748
  11. ^ Wagner, Robert A. (May 1975). "On the complexity of the Extended String-to-String Correction Problem". Proceedings of seventh annual ACM symposium on Theory of computing - STOC '75. pp. 218–223. doi:10.1145/800116.803771. ISBN 9781450374194. S2CID 18705107.
  12. ^ Friedman, Erich. "Corral Puzzles are NP-complete" (PDF). Retrieved 17 August 2021.
  13. ^ Yato, Takauki (2003). Complexity and Completeness of Finding Another Solution and its Application to Puzzles. CiteSeerX 10.1.1.103.8380.
  14. ^ Malte Helmert, Complexity results for standard benchmark domains in planning, Artificial Intelligence 143(2):219-262, 2003.
  15. ^ "HASHIWOKAKERO Is NP-Complete".
  16. ^ Holzer & Ruepp (2007)
  17. ^ Takahiro, Seta (5 February 2002). "The complexities of puzzles, cross sum and their another solution problems (ASP)" (PDF). Retrieved 18 November 2018.
  18. ^ Nguyen, Viet-Ha; Perrot, Kévin; Vallet, Mathieu (24 June 2020). "NP-completeness of the game KingdominoTM". Theoretical Computer Science. 822: 23–35. doi:10.1016/j.tcs.2020.04.007. ISSN 0304-3975. S2CID 218552723.
  19. ^ Kölker, Jonas (2012). "Kurodoko is NP-complete" (PDF). Journal of Information Processing. 20 (3): 694–706. doi:10.2197/ipsjjip.20.694. S2CID 46486962. Archived from the original (PDF) on 12 February 2020.
  20. ^ Alexandersson, Per; Restadh, Petter (2020). "LaserTank is NP-Complete". Mathematical Aspects of Computer and Information Sciences. Lecture Notes in Computer Science. Vol. 11989. Springer International Publishing. pp. 333–338. arXiv:1908.05966. doi:10.1007/978-3-030-43120-4_26. ISBN 978-3-030-43119-8. S2CID 201058355.
  21. ^ Cormode, Graham (2004). The hardness of the lemmings game, or Oh no, more NP-completeness proofs (PDF).
  22. ^ Light Up is NP-Complete
  23. ^ Friedman, Erich (27 March 2012). "Pearl Puzzles are NP-complete". Archived from the original on 4 February 2012.
  24. ^ Kaye (2000)
  25. ^ Allan Scott, Ulrike Stege, Iris van Rooij, Minesweeper may not be NP-complete but is hard nonetheless, The Mathematical Intelligencer 33:4 (2011), pp. 5–17.
  26. ^ Holzer, Markus; Klein, Andreas; Kutrib, Martin; Ruepp, Oliver (2011). "Computational Complexity of NURIKABE". Fundamenta Informaticae. 110 (1–4): 159–174. doi:10.3233/FI-2011-534.
  27. ^ Nakai, Kenichiro; Takenaga, Yasuhiko (2012). "NP-Completeness of Pandemic". Journal of Information Processing. 20 (3): 723–726. doi:10.2197/ipsjjip.20.723. ISSN 1882-6652.
  28. ^ Demaine, Erik; Eisenstat, Sarah; Rudoy, Mikhail (2018). Solving the Rubik's Cube Optimally is NP-complete. 35th Symposium on Theoretical Aspects of Computer Science (STACS 2018). doi:10.4230/LIPIcs.STACS.2018.24.
  29. ^ a b Sato, Takayuki; Seta, Takahiro (1987). Complexity and Completeness of Finding Another Solution and Its Application to Puzzles (PDF). International Symposium on Algorithms (SIGAL 1987).
  30. ^ Nukui; Uejima (March 2007). "ASP-Completeness of the Slither Link Puzzle on Several Grids". Ipsj Sig Notes. 2007 (23): 129–136.
  31. ^ Kölker, Jonas (2012). "Selected Slither Link Variants are NP-complete". Journal of Information Processing. 20 (3): 709–712. doi:10.2197/ipsjjip.20.709.
  32. ^ A SURVEY OF NP-COMPLETE PUZZLES, Section 23; Graham Kendall, Andrew Parkes, Kristian Spoerer; March 2008. (icga2008.pdf)
  33. ^ Demaine, Eric D.; Hohenberger, Susan; Liben-Nowell, David (25–28 July 2003). Tetris is Hard, Even to Approximate (PDF). Proceedings of the 9th International Computing and Combinatorics Conference (COCOON 2003). Big Sky, Montana.
  34. ^ Lim, Andrew (1998), "The berth planning problem", Operations Research Letters, 22 (2–3): 105–110, doi:10.1016/S0167-6377(98)00010-8, MR 1653377
  35. ^ J. Bonneau, "Bitcoin mining is NP-hard"
  36. ^ Galil, Zvi; Megiddo, Nimrod (October 1977). "Cyclic ordering is NP-complete". Theoretical Computer Science. 5 (2): 179–182. doi:10.1016/0304-3975(77)90005-6.
  37. ^ Whitfield, James Daniel; Love, Peter John; Aspuru-Guzik, Alán (2013). "Computational complexity in electronic structure". Phys. Chem. Chem. Phys. 15 (2): 397–411. arXiv:1208.3334. Bibcode:2013PCCP...15..397W. doi:10.1039/C2CP42695A. PMID 23172634. S2CID 12351374.
  38. ^ Agol, Ian; Hass, Joel; Thurston, William (19 May 2002). "3-manifold knot genus is NP-complete". Proceedings of the thiry-fourth annual ACM symposium on Theory of computing. STOC '02. New York, NY, USA: Association for Computing Machinery. pp. 761–766. arXiv:math/0205057. doi:10.1145/509907.510016. ISBN 978-1-58113-495-7. S2CID 10401375.
  39. ^ Çivril, Ali; Magdon-Ismail, Malik (2009), "On selecting a maximum volume sub-matrix of a matrix and related problems" (PDF), Theoretical Computer Science, 410 (47–49): 4801–4811, doi:10.1016/j.tcs.2009.06.018, MR 2583677, archived from the original (PDF) on 3 February 2015
  40. ^ Peter Downey, Benton Leong, and Ravi Sethi. "Computing Sequences with Addition Chains" SIAM J. Comput., 10(3), 638–646, 1981
  41. ^ D. J. Bernstein, "Pippinger's exponentiation algorithm" (draft)
  42. ^ Hurkens, C.; Iersel, L. V.; Keijsper, J.; Kelk, S.; Stougie, L.; Tromp, J. (2007). "Prefix reversals on binary and ternary strings". SIAM J. Discrete Math. 21 (3): 592–611. arXiv:math/0602456. doi:10.1137/060664252.
  43. ^ a b Manders, Kenneth; Adleman, Leonard (1976). "NP-complete decision problems for quadratic polynomials". Proceedings of the eighth annual ACM symposium on Theory of computing - STOC '76. pp. 23–29. doi:10.1145/800113.803627. ISBN 9781450374149. S2CID 18885088.
  44. ^ Bein, W. W.; Larmore, L. L.; Latifi, S.; Sudborough, I. H. (1 January 2002). "Block sorting is hard". Proceedings International Symposium on Parallel Architectures, Algorithms and Networks. I-SPAN'02. pp. 307–312. doi:10.1109/ISPAN.2002.1004305. ISBN 978-0-7695-1579-3. S2CID 32222403.
  45. ^ Barry Arthur Cipra, "The Ising Model Is NP-Complete", SIAM News, Vol 33, No 6.

References

[edit]

General

Specific problems

[edit]