List of NP-complete problems

From Wikipedia, the free encyclopedia
Jump to navigation Jump to search

This is a list of some of the more commonly known problems that are NP-complete when expressed as decision problems. As there are hundreds 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.[11]

Mathematical programming[edit]

Formal languages and string processing[edit]

Games and puzzles[edit]

Other[edit]

NP-complete special cases include the minimum maximal matching problem,[81] which is essentially equal to the edge dominating set problem (see above).

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. ^ Garey & Johnson (1979): SP1
  4. ^ Garey & Johnson (1979): GT18
  5. ^ Garey & Johnson (1979): ND5
  6. ^ Garey & Johnson (1979): ND25, ND27
  7. ^ Garey & Johnson (1979): GT19
  8. ^ Garey & Johnson (1979): GT5
  9. ^ Garey & Johnson (1979): GT3
  10. ^ Garey & Johnson (1979): GT2
  11. ^ Garey & Johnson (1979): ND2
  12. ^ Garey & Johnson (1979): GT40
  13. ^ Garey & Johnson (1979): GT17
  14. ^ Garey & Johnson (1979): ND1
  15. ^ Garey & Johnson (1979): SP2
  16. ^ Garey & Johnson (1979): GT7
  17. ^ Garey & Johnson (1979): GT8
  18. ^ Garey & Johnson (1979): GT52
  19. ^ Garey & Johnson (1979): GT4
  20. ^ Garey & Johnson (1979): GT11, GT12, GT13, GT14, GT15, GT16, ND14
  21. ^ Garey & Johnson (1979): GT34
  22. ^ Garey & Johnson (1979): GT37, GT38, GT39
  23. ^ Garey & Johnson (1979): ND29
  24. ^ Garey & Johnson (1979): GT25, ND16
  25. ^ Garey & Johnson (1979): GT20
  26. ^ Garey & Johnson (1979): GT23
  27. ^ Garey & Johnson (1979): GT59
  28. ^ Garey & Johnson (1979): GT61
  29. ^ 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
  30. ^ a b c d Arnborg, Corneil & Proskurowski (1987)
  31. ^ Garey & Johnson (1979): SP5, SP8
  32. ^ Garey & Johnson (1979): SP4
  33. ^ Garey & Johnson (1979): ND3
  34. ^ a b Garg, Ashim; Tamassia, Roberto (1995). "On the computational complexity of upward and rectilinear planarity testing". Lecture Notes in Computer Science. 894/1995. pp. 286–297. doi:10.1007/3-540-58950-3_384. ISBN 978-3-540-58950-1.
  35. ^ Garey & Johnson (1979): GT1
  36. ^ Garey & Johnson (1979): SP15
  37. ^ Garey & Johnson (1979): SR1
  38. ^ Garey & Johnson (1979): MP9
  39. ^ Garey & Johnson (1979): ND22, ND23
  40. ^ Garey & Johnson (1979): ND24
  41. ^ Garey & Johnson (1979): MP1
  42. ^ Garey & Johnson (1979): SP16
  43. ^ Garey & Johnson (1979): SP12
  44. ^ Garey & Johnson (1979): ND43
  45. ^ NP-complete decision problems for Quadratic Polynomials
  46. ^ Garey & Johnson (1979): SP13
  47. ^ 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
  48. ^ Garey & Johnson (1979): SR10
  49. ^ Garey & Johnson (1979): SR11
  50. ^ Garey & Johnson (1979): SR8
  51. ^ Garey & Johnson (1979): SR20
  52. ^ Malte Helmert, Complexity results for standard benchmark domains in planning, Artificial Intelligence 143(2):219-262, 2003.
  53. ^ Yato, Takauki (2003). Complexity and Completeness of Finding Another Solution and its Application to Puzzles. CiteSeerX 10.1.1.103.8380.
  54. ^ "HASHIWOKAKERO Is NP-Complete".
  55. ^ Holzer & Ruepp (2007)
  56. ^ Garey & Johnson (1979): GP15
  57. ^ 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.
  58. ^ 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.
  59. ^ Alexandersson, Per; Restadh, Petter (2020). "LaserTank is NP-Complete". Mathematical Aspects of Computer and Information Sciences. Lecture Notes in Computer Science. 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.
  60. ^ Cormode, Graham (2004). The hardness of the lemmings game, or Oh no, more NP-completeness proofs (PDF).
  61. ^ Light Up is NP-Complete
  62. ^ Friedman, Erich (27 March 2012). "Pearl Puzzles are NP-complete".
  63. ^ Kaye (2000)
  64. ^ 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.
  65. ^ Garey & Johnson (1979): GT56
  66. ^ 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.
  67. ^ 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.
  68. ^ http://pbg.cs.illinois.edu/papers/set.pdf
  69. ^ 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).
  70. ^ Nukui; Uejima (March 2007). "ASP-Completeness of the Slither Link Puzzle on Several Grids". Ipsj Sig Notes. 2007 (23): 129–136.
  71. ^ 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.
  72. ^ A SURVEY OF NP-COMPLETE PUZZLES, Section 23; Graham Kendall, Andrew Parkes, Kristian Spoerer; March 2008. (icga2008.pdf)
  73. ^ 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.
  74. ^ 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
  75. ^ J. Bonneau, "Bitcoin mining is NP-hard
  76. ^ Garey & Johnson (1979): LO1
  77. ^ Garey & Johnson (1979): p. 48
  78. ^ Garey & Johnson (1979): SR31
  79. ^ Garey & Johnson (1979): GT6
  80. ^ Minimum Independent Dominating Set
  81. ^ Garey & Johnson (1979): GT10
  82. ^ Garey & Johnson (1979): GT49
  83. ^ Garey & Johnson (1979): LO5
  84. ^ https://web.archive.org/web/20150203193923/http://www.meliksah.edu.tr/acivril/max-vol-original.pdf
  85. ^ Peter Downey, Benton Leong, and Ravi Sethi. "Computing Sequences with Addition Chains" SIAM J. Comput., 10(3), 638–646, 1981
  86. ^ D. J. Bernstein, "Pippinger's exponentiation algorithm (draft)
  87. ^ Kashiwabara & Fujisawa (1979); Ohtsuki et al. (1979); Lengauer (1981).
  88. ^ 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.
  89. ^ Garey & Johnson (1979): GT48
  90. ^ Garey & Johnson (1979): ND13
  91. ^ Garey & Johnson (1979): SP3
  92. ^ Garey & Johnson (1979): SR33
  93. ^ Bein, W. W.; Larmore, L. L.; Latifi, S.; Sudborough, I. H. (1 January 2002). Block sorting is hard. International Symposium on Parallel Architectures, Algorithms and Networks, 2002. I-SPAN '02. Proceedings. pp. 307–312. doi:10.1109/ISPAN.2002.1004305. ISBN 978-0-7695-1579-3. S2CID 32222403.
  94. ^ Barry Arthur Cipra, "The Ising Model Is NP-Complete", SIAM News, Vol 33, No 6.

References[edit]

General

Specific problems

External links[edit]