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 (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,[78] 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 
  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 "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. 
  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. ^ Garey & Johnson (1979): SP13
  46. ^ Lanctot, J. Kevin; Li, Ming; Ma, Bin; Wang, Shaojiu; Zhang, Louxin (2003), "Distinguishing string selection problems", Information and Computation, 185 (1): 41–55, MR 1994748, doi:10.1016/S0890-5401(03)00057-9 
  47. ^ Garey & Johnson (1979): SR10
  48. ^ Garey & Johnson (1979): SR11
  49. ^ Garey & Johnson (1979): SR8
  50. ^ Garey & Johnson (1979): SR20
  51. ^ a b Gualà, L.; Leucci, S.; Natale, E. (2014). "Bejeweled, Candy Crush and other Match-Three Games are (NP-)Hard". 2014 IEEE Conference on Computational Intelligence and Games. pp. 1–8. arXiv:1403.5830Freely accessible. doi:10.1109/CIG.2014.6932866. 
  52. ^ Walsh, Toby (2014). "Candy Crush is NP-hard". arXiv:1403.1911Freely accessible. 
  53. ^ a b c d e G. Aloupis; E. D. Demaine; A. Guo (2012-03-09). "Classic Nintendo Games are (NP-)Hard". arXiv:1203.1895Freely accessible. 
  54. ^ Malte Helmert, Complexity results for standard benchmark domains in planning, Artificial Intelligence Journal 143(2):219-262, 2003.
  55. ^ Yato, Takauki (2003). "Complexity and Completeness of Finding Another Solution and its Application to Puzzles". CiteSeerX 10.1.1.103.8380Freely accessible. 
  56. ^ "HASHIWOKAKERO Is NP-Complete". 
  57. ^ Holzer & Ruepp (2007)
  58. ^ Garey & Johnson (1979): GP15
  59. ^ Kölker, Jonas (2012). "Kurodoko is NP-complete". 
  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 (2012-03-27). "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. ^ 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). 
  67. ^ Nukui; Uejima. "ASP-Completeness of the Slither Link Puzzle on Several Grids". 
  68. ^ Kölker, Jonas (2012). "Selected Slither Link Variants are NP-complete". 
  69. ^ A SURVEY OF NP-COMPLETE PUZZLES, Section 23; Graham Kendall, Andrew Parkes, Kristian Spoerer; March 2008. (icga2008.pdf)
  70. ^ Demaine, Eric D.; Hohenberger, Susan; Liben-Nowell, David (July 25–28, 2003). Tetris is Hard, Even to Approximate (PDF). Proceedings of the 9th International Computing and Combinatorics Conference (COCOON 2003). Big Sky, Montana. 
  71. ^ Lim, Andrew (1998), "The berth planning problem", Operations Research Letters, 22 (2-3): 105–110, MR 1653377, doi:10.1016/S0167-6377(98)00010-8 
  72. ^ J. Bonneau, "Bitcoin mining is NP-hard
  73. ^ Garey & Johnson (1979): LO1
  74. ^ Garey & Johnson (1979): p. 48
  75. ^ Garey & Johnson (1979): SR31
  76. ^ Garey & Johnson (1979): GT6
  77. ^ Minimum Independent Dominating Set
  78. ^ Garey & Johnson (1979): GT10
  79. ^ Garey & Johnson (1979): GT49
  80. ^ Garey & Johnson (1979): LO5
  81. ^ https://web.archive.org/web/20150203193923/http://www.meliksah.edu.tr/acivril/max-vol-original.pdf
  82. ^ Peter Downey, Benton Leong, and Ravi Sethi. "Computing Sequences with Addition Chains" SIAM J. Comput., 10(3), 638–646, 1981
  83. ^ D. J. Bernstein, "Pippinger's exponentiation algorithm (draft)
  84. ^ Kashiwabara & Fujisawa (1979); Ohtsuki et al. (1979); Lengauer (1981).
  85. ^ 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.
  86. ^ Garey & Johnson (1979): GT48
  87. ^ Garey & Johnson (1979): ND13
  88. ^ Garey & Johnson (1979): SP3
  89. ^ Garey & Johnson (1979): SR33
  90. ^ Bein, W. W.; Larmore, L. L.; Latifi, S.; Sudborough, I. H. (2002-01-01). "Block sorting is hard". International Symposium on Parallel Architectures, Algorithms and Networks, 2002. I-SPAN '02. Proceedings: 307–312. doi:10.1109/ISPAN.2002.1004305. 
  91. ^ Barry A. Cipra, "The Ising Model Is NP-Complete", SIAM News, Vol 33, No 6.

References[edit]

General

Specific problems

External links[edit]