List of NP-complete problems

From HandWiki
Short description: none
This is a dynamic list and may never be able to satisfy particular standards for completeness. You can help by expanding it with reliably sourced entries.

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).

Graphs and hypergraphs

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

Formal languages and string processing

Games and puzzles

Other

  • Berth allocation problem[35]
  • Betweenness
  • Assembling an optimal Bitcoin block.[36]
  • Boolean satisfiability problem (SAT).[2][3]:LO1 There are many variations that are also NP-complete. An important variant is where each clause has exactly three literals (3SAT), since it is used in the proof of many other NP-completeness results.[3]:p. 48
  • Circuit satisfiability problem
  • Conjunctive Boolean query[3]:SR31
  • Cyclic ordering[37]
  • Exact cover problem. Remains NP-complete for 3-sets. Solvable in polynomial time for 2-sets (this is a matching).[2][3]:SP2
  • Finding the global minimum solution of a Hartree-Fock problem[38]
  • Upward planarity testing[8]
  • Hospitals-and-residents problem with couples
  • Knot genus[39]
  • Latin square completion (the problem of determining if a partially filled square can be completed)
  • Maximum 2-satisfiability[3]:LO5
  • Maximum volume submatrix – Problem of selecting the best conditioned subset of a larger [math]\displaystyle{ m\times n }[/math] matrix. This class of problem is associated with Rank revealing QR factorizations and D optimal experimental design.[40]
  • Minimal addition chains for sequences.[41] The complexity of minimal addition chains for individual numbers is unknown.[42]
  • Modal logic S5-Satisfiability
  • Pancake sorting distance problem for strings[43]
  • Solubility of two-variable quadratic polynomials over the integers.[44] Given positive integers [math]\displaystyle{ \textstyle A,B,C }[/math], decide existence of positive integers [math]\displaystyle{ x,y }[/math] such that [math]\displaystyle{ Ax^2+By-C=0 }[/math]
  • By the same article[44] existence of bounded modular square roots with arbitrarily composite modulus. Given positive integers [math]\displaystyle{ \textstyle A,B,C \geq 0 }[/math], decide existence of an integer [math]\displaystyle{ x\in[0,C] }[/math] such that [math]\displaystyle{ x^2\equiv A\bmod B }[/math]. The problem remains NP-complete even if a prime factorization of [math]\displaystyle{ B }[/math] is provided.
  • Second order instantiation[citation needed]
  • Serializability of database histories[3]:SR33
  • Set cover (also called minimum cover problem) This is equivalent, by transposing the incidence matrix, to the hitting set problem.[2][3]:SP5, SP8
  • Set packing[2][3]:SP3
  • Set splitting problem[3]:SP4
  • Scheduling to minimize weighted completion time
  • Block Sorting[45] (Sorting by Block Moves)
  • Sparse approximation
  • Variations of the Steiner tree problem. Specifically, with the discretized Euclidean metric, rectilinear metric. The problem is known to be NP-hard with the (non-discretized) Euclidean metric.[3]:ND13
  • Three-dimensional Ising model[46]

See also

Notes

  1. ↑ Grigoriev & Bodlaender (2007).
  2. ↑ 2.00 2.01 2.02 2.03 2.04 2.05 2.06 2.07 2.08 2.09 2.10 2.11 2.12 2.13 2.14 2.15 2.16 (Karp 1972)
  3. ↑ 3.00 3.01 3.02 3.03 3.04 3.05 3.06 3.07 3.08 3.09 3.10 3.11 3.12 3.13 3.14 3.15 3.16 3.17 3.18 3.19 3.20 3.21 3.22 3.23 3.24 3.25 3.26 3.27 3.28 3.29 3.30 3.31 3.32 3.33 3.34 3.35 3.36 3.37 3.38 3.39 3.40 3.41 3.42 3.43 3.44 3.45 3.46 3.47 3.48 3.49 3.50 3.51 3.52 3.53 3.54 3.55 3.56 (Garey Johnson)
  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, Bibcode: 2006physics...8255B 
  6. ↑ 6.0 6.1 (Arnborg Corneil)
  7. ↑ (Kashiwabara Fujisawa); (Ohtsuki Mori); (Lengauer 1981).
  8. ↑ 8.0 8.1 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. 
  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 
  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. https://dl.acm.org/doi/10.1145/800116.803771. 
  12. ↑ Friedman, Erich. "Corral Puzzles are NP-complete". https://erich-friedman.github.io/papers/corral.pdf. 
  13. ↑ Yato, Takauki (2003). Complexity and Completeness of Finding Another Solution and its Application to Puzzles. 
  14. ↑ Malte Helmert, Complexity results for standard benchmark domains in planning, Artificial Intelligence 143(2):219-262, 2003.
  15. ↑ "HASHIWOKAKERO Is NP-Complete". http://www.cs.au.dk/~koda/hashiwokakero. 
  16. ↑ (Holzer Ruepp)
  17. ↑ Takahiro, Seta (February 5, 2002). "The complexities of puzzles, cross sum and their another solution problems (ASP)". http://www-imai.is.s.u-tokyo.ac.jp/~seta/paper/senior_thesis/seniorthesis.pdf. 
  18. ↑ Nguyen, Viet-Ha; Perrot, Kévin; Vallet, Mathieu (2020-06-24). "NP-completeness of the game KingdominoTM" (in en). Theoretical Computer Science 822: 23–35. doi:10.1016/j.tcs.2020.04.007. ISSN 0304-3975. 
  19. ↑ Kölker, Jonas (2012). "Kurodoko is NP-complete". Journal of Information Processing 20 (3): 694–706. doi:10.2197/ipsjjip.20.694. https://pdfs.semanticscholar.org/4971/aa310e07aaa07c1ba7299f519b39ba5c5195.pdf. 
  20. ↑ Alexandersson, Per; Restadh, Petter (2020). "LaserTank is NP-Complete" (in en). Mathematical Aspects of Computer and Information Sciences. Lecture Notes in Computer Science. 11989. Springer International Publishing. pp. 333–338. doi:10.1007/978-3-030-43120-4_26. ISBN 978-3-030-43119-8. 
  21. ↑ Cormode, Graham (2004). "The hardness of the lemmings game, or Oh no, more NP-completeness proofs". http://dimacs.rutgers.edu/~graham/pubs/papers/cormodelemmings.pdf. 
  22. ↑ Light Up is NP-Complete
  23. ↑ Friedman, Erich (2012-03-27). "Pearl Puzzles are NP-complete". http://www2.stetson.edu/~efriedma/papers/pearl/pearl.html. 
  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 (2004). "On The NP-Completeness of The NURIKABE Pencil Puzzle and Variants Thereof". Proceedings of the 3rd International Conference on Fun with Algorithms. https://pdfs.semanticscholar.org/4855/b7160c651c8cc883def72348463fd77cdbed.pdf. 
  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. ↑ Chaudhuri, Kamalika; Godfrey, Brighten; Ratajczak, David; Wee, Hoeteck (2003). On the Complexity of the Game of Set. http://pbg.cs.illinois.edu/papers/set.pdf. 
  30. ↑ 30.0 30.1 Sato, Takayuki; Seta, Takahiro (1987). "Complexity and Completeness of Finding Another Solution and Its Application to Puzzles". International Symposium on Algorithms (SIGAL 1987). http://www-imai.is.s.u-tokyo.ac.jp/~yato/data2/SIGAL87-2.pdf. 
  31. ↑ Nukui; Uejima (March 2007). "ASP-Completeness of the Slither Link Puzzle on Several Grids". Ipsj Sig Notes 2007 (23): 129–136. http://ci.nii.ac.jp/naid/110006249219/en/. 
  32. ↑ 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. 
  33. ↑ A SURVEY OF NP-COMPLETE PUZZLES, Section 23; Graham Kendall, Andrew Parkes, Kristian Spoerer; March 2008. (icga2008.pdf)
  34. ↑ Demaine, Eric D.; Hohenberger, Susan; Liben-Nowell, David (25–28 July 2003). "Tetris is Hard, Even to Approximate". Proceedings of the 9th International Computing and Combinatorics Conference (COCOON 2003). Big Sky, Montana. http://erikdemaine.org/papers/Tetris_COCOON2003/paper.pdf. 
  35. ↑ Lim, Andrew (1998), "The berth planning problem", Operations Research Letters 22 (2–3): 105–110, doi:10.1016/S0167-6377(98)00010-8 
  36. ↑ J. Bonneau, "Bitcoin mining is NP-hard"
  37. ↑ 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. 
  38. ↑ Whitfield, James Daniel; Love, Peter John; Aspuru-Guzik, Alán (2013). "Computational complexity in electronic structure". Phys. Chem. Chem. Phys. 15 (2): 397–411. doi:10.1039/C2CP42695A. PMID 23172634. Bibcode: 2013PCCP...15..397W. https://doi.org/10.1039/C2CP42695A. 
  39. ↑ Agol, Ian; Hass, Joel; Thurston, William (2002-05-19). "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. doi:10.1145/509907.510016. ISBN 978-1-58113-495-7. https://doi.org/10.1145/509907.510016. 
  40. ↑ "Archived copy". http://www.meliksah.edu.tr/acivril/max-vol-original.pdf. 
  41. ↑ Peter Downey, Benton Leong, and Ravi Sethi. "Computing Sequences with Addition Chains" SIAM J. Comput., 10(3), 638–646, 1981
  42. ↑ D. J. Bernstein, "Pippinger's exponentiation algorithm" (draft)
  43. ↑ 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. doi:10.1137/060664252. 
  44. ↑ 44.0 44.1 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. https://dl.acm.org/doi/10.1145/800113.803627. 
  45. ↑ Bein, W. W.; Larmore, L. L.; Latifi, S.; Sudborough, I. H. (2002-01-01). "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. 
  46. ↑ Barry Arthur Cipra, "The Ising Model Is NP-Complete", SIAM News, Vol 33, No 6.

References

General

Specific problems

External links



Retrieved from "https://handwiki.org/wiki/index.php?title=List_of_NP-complete_problems&oldid=3386270"