List of NP-complete problems

From Wikipedia, the free encyclopedia
Jump to: navigation, 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 (see 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,[76] 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. ^ a b Arnborg, Corneil & Proskurowski (1987)
  30. ^ Garey & Johnson (1979): SP5, SP8
  31. ^ Garey & Johnson (1979): SP4
  32. ^ Garey & Johnson (1979): ND3
  33. ^ a b "On the computational complexity of upward and rectilinear planarity testing". Lecture Notes in Computer Science. 894/1995. 1995. pp. 286–297. doi:10.1007/3-540-58950-3_384. 
  34. ^ Garey & Johnson (1979): GT1
  35. ^ Garey & Johnson (1979): SP15
  36. ^ Garey & Johnson (1979): SR1
  37. ^ Garey & Johnson (1979): MP9
  38. ^ Garey & Johnson (1979): ND22, ND23
  39. ^ Garey & Johnson (1979): ND24
  40. ^ Garey & Johnson (1979): MP1
  41. ^ Garey & Johnson (1979): SP16
  42. ^ Garey & Johnson (1979): SP12
  43. ^ Garey & Johnson (1979): ND43
  44. ^ Garey & Johnson (1979): SP13
  45. ^ 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 .
  46. ^ Garey & Johnson (1979): SR10
  47. ^ Garey & Johnson (1979): SR11
  48. ^ Garey & Johnson (1979): SR8
  49. ^ Garey & Johnson (1979): SR20
  50. ^ a b L. Gualà, S. Leucci, E. Natale (2014). "Bejeweled, Candy Crush and other Match-Three Games are (NP-)Hard". 
  51. ^ Walsh, Toby (2014). "Candy Crush is NP-hard". 
  52. ^ Malte Helmert, Complexity results for standard benchmark domains in planning, Artificial Intelligence Journal 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. ^ Holzer & Ruepp (2007)
  55. ^ Garey & Johnson (1979): GP15
  56. ^ Kölker, Jonas (2012). "Kurodoko is NP-complete". 
  57. ^ Cormode, Graham (2004). "The hardness of the lemmings game, or Oh no, more NP-completeness proofs". 
  58. ^ Light Up is NP-Complete
  59. ^ Friedman, Erich (2012-03-27). "Pearl Puzzles are NP-complete". 
  60. ^ Kaye (2000)
  61. ^ 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.
  62. ^ Garey & Johnson (1979): GT56
  63. ^ Yato; Seta. "Complexity and Completeness of Finding Another Solution and Its Application to Puzzles". 
  64. ^ Yato. "Complexity and completeness of finding another solution and its application to puzzles". 
  65. ^ Nukui; Uejima. "ASP-Completeness of the Slither Link Puzzle on Several Grids". 
  66. ^ Kölker, Jonas (2012). "Selected Slither Link Variants are NP-complete". 
  67. ^ G. Aloupis, E. D. Demaine, A. Guo (2012-03-09). "Classic Nintendo Games are (NP-)Hard". 
  68. ^ Demaine, Eric D.; Hohenberger, Susan; Liben-Nowell, David (July 25–28, 2003). "Tetris is Hard, Even to Approximate". Proceedings of the 9th International Computing and Combinatorics Conference (COCOON 2003). Big Sky, Montana. 
  69. ^ 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 .
  70. ^ J. Bonneau, "Bitcoin mining is NP-hard
  71. ^ Garey & Johnson (1979): LO1
  72. ^ Garey & Johnson (1979): p. 48
  73. ^ Garey & Johnson (1979): SR31
  74. ^ Garey & Johnson (1979): GT6
  75. ^ Minimum Independent Dominating Set
  76. ^ Garey & Johnson (1979): GT10
  77. ^ Garey & Johnson (1979): GT49
  78. ^ Garey & Johnson (1979): LO5
  79. ^ http://www.cs.rpi.edu/~civria/max-vol-inapprox.pdf
  80. ^ Peter Downey, Benton Leong, and Ravi Sethi. "Computing Sequences with Addition Chains" SIAM J. Comput., 10(3), 638–646, 1981
  81. ^ D. J. Bernstein, "Pippinger's exponentiation algorithm (draft)
  82. ^ a b Arnborg, Corneil & Proskurowski (1987)
  83. ^ Kashiwabara & Fujisawa (1979); Ohtsuki et al. (1979); Lengauer (1981).
  84. ^ Hurkens, C., Iersel, L. V., Keijsper, J., Kelk, S., Stougie, L. and Tromp J. "Prefix reversals on binary and ternary strings". SIAM J. Discrete Math. 21(3)(2007) 592–611.
  85. ^ Garey & Johnson (1979): GT48
  86. ^ Garey & Johnson (1979): ND13
  87. ^ Garey & Johnson (1979): SP3
  88. ^ Garey & Johnson (1979): SR33
  89. ^ Barry A. Cipra, "The Ising Model Is NP-Complete", SIAM News, Vol 33, No 6.

References[edit]

General
Specific problems
  • Holzer, Markus; Ruepp, Oliver (2007). "The Troubles of Interior Design–A Complexity Analysis of the Game Heyawake". "Proceedings, 4th International Conference on Fun with Algorithms, LNCS 4475". Springer, Berlin/Heidelberg. pp. 198–212. doi:10.1007/978-3-540-72914-3_18. ISBN 978-3-540-72913-6. 
  • Cormode, Graham (2004). "The hardness of the lemmings game, or Oh no, more NP-completeness proofs". "Proceedings of Third International Conference on Fun with Algorithms (FUN 2004)". pp. 65–76. 

External links[edit]