List of NP-complete problems: Difference between revisions
Content deleted Content added
m →Games and puzzles: added laserTank |
Added Kingdomino and Pandemic to list of NP-complete games |
||
| Line 92: | Line 92: | ||
*([[Generalized game|Generalized]]) [[Instant Insanity]]<ref>{{harvtxt|Garey|Johnson|1979}}: GP15</ref> |
*([[Generalized game|Generalized]]) [[Instant Insanity]]<ref>{{harvtxt|Garey|Johnson|1979}}: GP15</ref> |
||
*[[Kakuro|Kakuro (Cross Sums)]] |
*[[Kakuro|Kakuro (Cross Sums)]] |
||
*[[Kingdomino]]<ref>{{Cite journal|last=Nguyen|first=Viet-Ha|last2=Perrot|first2=Kévin|last3=Vallet|first3=Mathieu|date=2020-06-24|title=NP-completeness of the game KingdominoTM|url=http://www.sciencedirect.com/science/article/pii/S0304397520302115|journal=Theoretical Computer Science|language=en|volume=822|pages=23–35|doi=10.1016/j.tcs.2020.04.007|issn=0304-3975}}</ref> |
|||
*[[Kuromasu]] (also known as Kurodoko)<ref name="Kölker12b">{{cite journal | last = Kölker | first = Jonas | title = Kurodoko is NP-complete | journal = Journal of Information Processing | volume = 20 | issue = 3 | pages = 694–706 | year = 2012 | doi = 10.2197/ipsjjip.20.694 }}</ref> |
*[[Kuromasu]] (also known as Kurodoko)<ref name="Kölker12b">{{cite journal | last = Kölker | first = Jonas | title = Kurodoko is NP-complete | journal = Journal of Information Processing | volume = 20 | issue = 3 | pages = 694–706 | year = 2012 | doi = 10.2197/ipsjjip.20.694 }}</ref> |
||
*[[LaserTank]] <ref>{{cite journal |last1=Alexandersson |first1=Per |last2=Restadh |first2=Petter |title=LaserTank is NP-Complete |journal=Mathematical Aspects of Computer and Information Sciences |date=2020 |pages=333–338 |doi=10.1007/978-3-030-43120-4_26 |url=https://doi.org/10.1007/978-3-030-43120-4_26 |publisher=Springer International Publishing |language=en}}</ref> |
*[[LaserTank]] <ref>{{cite journal |last1=Alexandersson |first1=Per |last2=Restadh |first2=Petter |title=LaserTank is NP-Complete |journal=Mathematical Aspects of Computer and Information Sciences |date=2020 |pages=333–338 |doi=10.1007/978-3-030-43120-4_26 |url=https://doi.org/10.1007/978-3-030-43120-4_26 |publisher=Springer International Publishing |language=en}}</ref> |
||
| Line 103: | Line 104: | ||
*[[Nurikabe (puzzle)|Nurikabe]] |
*[[Nurikabe (puzzle)|Nurikabe]] |
||
*NxNxN [[Rubik's Cube]] (solved optimally) |
*NxNxN [[Rubik's Cube]] (solved optimally) |
||
*([[Generalized game|Generalized]]) [[Pandemic (board game)|Pandemic]]<ref>{{Cite journal|last=Nakai|first=Kenichiro|last2=Takenaga|first2=Yasuhiko|date=2012|title=NP-Completeness of Pandemic|url=https://doi.org/10.2197/ipsjjip.20.723|journal=Journal of Information Processing|volume=20|issue=3|pages=723–726|doi=10.2197/ipsjjip.20.723|issn=1882-6652}}</ref> |
|||
*[[SameGame]] |
*[[SameGame]] |
||
*([[Generalized game|Generalized]]) [[Set (card game)|Set]]<ref>http://pbg.cs.illinois.edu/papers/set.pdf</ref> |
*([[Generalized game|Generalized]]) [[Set (card game)|Set]]<ref>http://pbg.cs.illinois.edu/papers/set.pdf</ref> |
||
Revision as of 22:57, 18 July 2020
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
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).
- 1-planarity[1]
- 3-dimensional matching[2][3]
- Bipartite dimension[4]
- Capacitated minimum spanning tree[5]
- Route inspection problem (also called Chinese postman problem) for mixed graphs (having both directed and undirected edges). The program is solvable in polynomial time if the graph has all undirected or all directed edges. Variants include the rural postman problem.[6]
- Clique problem[2][7]
- Complete coloring, a.k.a. achromatic number[8]
- Domatic number[9]
- Dominating set, a.k.a. domination number[10]
- 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]
- Bandwidth problem[12]
- Clique cover problem[2][13]
- Rank coloring a.k.a. cycle rank
- Degree-constrained spanning tree[14]
- Exact cover problem. Remains NP-complete for 3-sets. Solvable in polynomial time for 2-sets (this is a matching).[2][15]
- Feedback vertex set[2][16]
- Feedback arc set[2][17]
- Graph homomorphism problem[18]
- Graph coloring[2][19]
- Graph partition into subgraphs of specific types (triangles, isomorphic subgraphs, Hamiltonian subgraphs, forests, perfect matchings) are known NP-complete. Partition into cliques is the same problem as coloring the complement of the given graph. A related problem is to find a partition that is optimal terms of the number of edges between parts.[20]
- Hamiltonian completion[21]
- Hamiltonian path problem, directed and undirected.[2][22]
- Longest path problem[23]
- Maximum bipartite subgraph or (especially with weighted edges) maximum cut.[2][24]
- Maximum independent set[25]
- Maximum Induced path[26]
- Graph intersection number[27]
- Metric dimension of a graph[28]
- Minimum k-cut
- Steiner tree, or Minimum spanning tree for a subset of the vertices of a graph.[2] (The minimum spanning tree for an entire graph is solvable in polynomial time.)
- Modularity maximization[29]
- Pathwidth[30]
- Set cover (also called minimum cover problem) This is equivalent, by transposing the incidence matrix, to the hitting set problem.[2][31]
- Set splitting problem[32]
- Shortest total path length spanning tree[33]
- Slope number two testing[34]
- Treewidth[30]
- Vertex cover[2][35]
Mathematical programming
- 3-partition problem[36]
- Bin packing problem[37]
- Knapsack problem, quadratic knapsack problem, and several variants[2][38]
- Variations on the Traveling salesman problem. The problem for graphs is NP-complete if the edge lengths are assumed integers. The problem for points on the plane is NP-complete with the discretized Euclidean metric and rectilinear metric. The problem is known to be NP-hard with the (non-discretized) Euclidean metric.[39]
- Bottleneck traveling salesman[40]
- Integer programming. The variant where variables are required to be 0 or 1, called zero-one linear programming, and several other variants are also NP-complete[2][41]
- Latin squares (The problem of determining if a partially filled square can be completed to form one)
- Numerical 3-dimensional matching[42]
- Partition problem[2][43]
- Quadratic assignment problem[44]
- Solving two-variable quadratic polynomials over the integers.[45] Given positive integers , find positive integers such that
- Quadratic programming (NP-hard in some cases, P if convex)
- Subset sum problem[46]
Formal languages and string processing
- Closest string[47]
- Longest common subsequence problem over multiple sequences[48]
- The bounded variant of the Post correspondence problem[49]
- Shortest common supersequence[50]
- String-to-string correction problem[51]
Games and puzzles
- Battleship
- Bulls and Cows, marketed as Master Mind: certain optimisation problems but not the game itself.
- Eternity II
- (Generalized) FreeCell[52]
- Fillomino[53]
- Hashiwokakero[54]
- Heyawake[55]
- (Generalized) Instant Insanity[56]
- Kakuro (Cross Sums)
- Kingdomino[57]
- Kuromasu (also known as Kurodoko)[58]
- LaserTank [59]
- Lemmings (with a polynomial time limit)[60]
- Light Up[61]
- Masyu[62]
- Minesweeper Consistency Problem[63] (but see Scott, Stege, & van Rooij[64])
- Nimber (or Grundy number) of a directed graph.[65]
- Numberlink
- Nonograms
- Nurikabe
- NxNxN Rubik's Cube (solved optimally)
- (Generalized) Pandemic[66]
- SameGame
- (Generalized) Set[67]
- Slither Link on a variety of grids[68][69][70]
- (Generalized) Sudoku[68][71]
- Problems related to Tetris[72]
- Verbal arithmetic
Other
- Berth allocation problem[73]
- Betweenness
- Assembling an optimal Bitcoin block.[74]
- Boolean satisfiability problem (SAT).[2][75] 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.[76]
- Conjunctive Boolean query[77]
- Cyclic ordering
- Circuit satisfiability problem
- Uncapacitated facility location problem
- Flow Shop Scheduling Problem
- Generalized assignment problem
- Upward planarity testing[34]
- Hospitals-and-residents problem with couples
- Some problems related to Job-shop scheduling
- Monochromatic triangle[78]
- Minimum maximal independent set a.k.a. minimum independent dominating set[79]
- NP-complete special cases include the minimum maximal matching problem,[80] which is essentially equal to the edge dominating set problem (see above).
- Maximum common subgraph isomorphism problem[81]
- Minimum degree spanning tree
- Minimum k-spanning tree
- Metric k-center
- Maximum 2-Satisfiability[82]
- Modal logic S5-Satisfiability
- Some problems related to Multiprocessor scheduling
- Maximum volume submatrix – Problem of selecting the best conditioned subset of a larger m x n matrix. This class of problem is associated with Rank revealing QR factorizations and D optimal experimental design.[83]
- Minimal addition chains for sequences.[84] The complexity of minimal addition chains for individual numbers is unknown.[85]
- Non-linear univariate polynomials over GF[2n], n the length of the input. Indeed, over any GF[qn].
- Open-shop scheduling
- Pathwidth,[30] or, equivalently, interval thickness, and vertex separation number[86]
- Pancake sorting distance problem for strings[87]
- k-Chinese postman
- Subgraph isomorphism problem[88]
- 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.[89]
- Set packing[2][90]
- Serializability of database histories[91]
- Scheduling to minimize weighted completion time
- Sparse approximation
- Block Sorting[92] (Sorting by Block Moves)
- Second order instantiation
- Treewidth[30]
- Testing whether a tree may be represented as Euclidean minimum spanning tree
- Three-dimensional Ising model[93]
- Vehicle routing problem
See also
- Existential theory of the reals#Complete problems
- Karp's 21 NP-complete problems
- List of PSPACE-complete problems
- Reduction (complexity)
Notes
- ^ Grigoriev & Bodlaender (2007).
- ^ a b c d e f g h i j k l m n o p q Karp (1972)
- ^ Garey & Johnson (1979): SP1
- ^ Garey & Johnson (1979): GT18
- ^ Garey & Johnson (1979): ND5
- ^ Garey & Johnson (1979): ND25, ND27
- ^ Garey & Johnson (1979): GT19
- ^ Garey & Johnson (1979): GT5
- ^ Garey & Johnson (1979): GT3
- ^ Garey & Johnson (1979): GT2
- ^ Garey & Johnson (1979): ND2
- ^ Garey & Johnson (1979): GT40
- ^ Garey & Johnson (1979): GT17
- ^ Garey & Johnson (1979): ND1
- ^ Garey & Johnson (1979): SP2
- ^ Garey & Johnson (1979): GT7
- ^ Garey & Johnson (1979): GT8
- ^ Garey & Johnson (1979): GT52
- ^ Garey & Johnson (1979): GT4
- ^ Garey & Johnson (1979): GT11, GT12, GT13, GT14, GT15, GT16, ND14
- ^ Garey & Johnson (1979): GT34
- ^ Garey & Johnson (1979): GT37, GT38, GT39
- ^ Garey & Johnson (1979): ND29
- ^ Garey & Johnson (1979): GT25, ND16
- ^ Garey & Johnson (1979): GT20
- ^ Garey & Johnson (1979): GT23
- ^ Garey & Johnson (1979): GT59
- ^ Garey & Johnson (1979): GT61
- ^ 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
- ^ a b c d Arnborg, Corneil & Proskurowski (1987)
- ^ Garey & Johnson (1979): SP5, SP8
- ^ Garey & Johnson (1979): SP4
- ^ Garey & Johnson (1979): ND3
- ^ 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.
- ^ Garey & Johnson (1979): GT1
- ^ Garey & Johnson (1979): SP15
- ^ Garey & Johnson (1979): SR1
- ^ Garey & Johnson (1979): MP9
- ^ Garey & Johnson (1979): ND22, ND23
- ^ Garey & Johnson (1979): ND24
- ^ Garey & Johnson (1979): MP1
- ^ Garey & Johnson (1979): SP16
- ^ Garey & Johnson (1979): SP12
- ^ Garey & Johnson (1979): ND43
- ^ NP-complete decision problems for Quadratic Polynomials
- ^ Garey & Johnson (1979): SP13
- ^ 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
- ^ Garey & Johnson (1979): SR10
- ^ Garey & Johnson (1979): SR11
- ^ Garey & Johnson (1979): SR8
- ^ Garey & Johnson (1979): SR20
- ^ Malte Helmert, Complexity results for standard benchmark domains in planning, Artificial Intelligence 143(2):219-262, 2003.
- ^ Yato, Takauki (2003). Complexity and Completeness of Finding Another Solution and its Application to Puzzles. CiteSeerX 10.1.1.103.8380.
- ^ "HASHIWOKAKERO Is NP-Complete".
- ^ Holzer & Ruepp (2007)
- ^ Garey & Johnson (1979): GP15
- ^ 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.
- ^ Kölker, Jonas (2012). "Kurodoko is NP-complete". Journal of Information Processing. 20 (3): 694–706. doi:10.2197/ipsjjip.20.694.
- ^ Alexandersson, Per; Restadh, Petter (2020). "LaserTank is NP-Complete". Mathematical Aspects of Computer and Information Sciences. Springer International Publishing: 333–338. doi:10.1007/978-3-030-43120-4_26.
- ^ Cormode, Graham (2004). The hardness of the lemmings game, or Oh no, more NP-completeness proofs (PDF).
- ^ Light Up is NP-Complete
- ^ Friedman, Erich (27 March 2012). "Pearl Puzzles are NP-complete".
- ^ Kaye (2000)
- ^ 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.
- ^ Garey & Johnson (1979): GT56
- ^ 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.
- ^ http://pbg.cs.illinois.edu/papers/set.pdf
- ^ 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).
- ^ Nukui; Uejima (March 2007). "ASP-Completeness of the Slither Link Puzzle on Several Grids". Ipsj Sig Notes. 2007 (23): 129–136.
- ^ 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.
- ^ A SURVEY OF NP-COMPLETE PUZZLES, Section 23; Graham Kendall, Andrew Parkes, Kristian Spoerer; March 2008. (icga2008.pdf)
- ^ 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.
{{cite conference}}: External link in|conferenceurl=|conferenceurl=ignored (|conference-url=suggested) (help) - ^ 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
- ^ J. Bonneau, "Bitcoin mining is NP-hard
- ^ Garey & Johnson (1979): LO1
- ^ Garey & Johnson (1979): p. 48
- ^ Garey & Johnson (1979): SR31
- ^ Garey & Johnson (1979): GT6
- ^ Minimum Independent Dominating Set
- ^ Garey & Johnson (1979): GT10
- ^ Garey & Johnson (1979): GT49
- ^ Garey & Johnson (1979): LO5
- ^ https://web.archive.org/web/20150203193923/http://www.meliksah.edu.tr/acivril/max-vol-original.pdf
- ^ Peter Downey, Benton Leong, and Ravi Sethi. "Computing Sequences with Addition Chains" SIAM J. Comput., 10(3), 638–646, 1981
- ^ D. J. Bernstein, "Pippinger's exponentiation algorithm (draft)
- ^ Kashiwabara & Fujisawa (1979); Ohtsuki et al. (1979); Lengauer (1981).
- ^ 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.
- ^ Garey & Johnson (1979): GT48
- ^ Garey & Johnson (1979): ND13
- ^ Garey & Johnson (1979): SP3
- ^ Garey & Johnson (1979): SR33
- ^ Bein, W. W.; Larmore, L. L.; Latifi, S.; Sudborough, I. H. (1 January 2002). Block sorting is hard. pp. 307–312. doi:10.1109/ISPAN.2002.1004305. ISBN 978-0-7695-1579-3.
{{cite book}}:|journal=ignored (help) - ^ Barry Arthur Cipra, "The Ising Model Is NP-Complete", SIAM News, Vol 33, No 6.
References
General
- Garey, Michael R.; Johnson, David S. (1979). Computers and Intractability: A Guide to the Theory of NP-Completeness. Series of Books in the Mathematical Sciences (1st ed.). New York: W. H. Freeman and Company. ISBN 9780716710455. MR 0519066. OCLC 247570676.. This book is a classic, developing the theory, then cataloguing many NP-Complete problems.
- Cook, S.A. (1971). "The complexity of theorem proving procedures". Proceedings, Third Annual ACM Symposium on the Theory of Computing, ACM, New York. pp. 151–158. doi:10.1145/800157.805047.
{{cite conference}}: Unknown parameter|booktitle=ignored (|book-title=suggested) (help) - Karp, Richard M. (1972). "Reducibility among combinatorial problems". In Miller, Raymond E.; Thatcher, James W. (eds.). Complexity of Computer Computations. Plenum. pp. 85–103.
{{cite book}}: Invalid|ref=harv(help) - Dunne, P.E. "An annotated list of selected NP-complete problems". COMP202, Dept. of Computer Science, University of Liverpool. Retrieved 21 June 2008.
- Crescenzi, P.; Kann, V.; Halldórsson, M.; Karpinski, M.; Woeginger, G. "A compendium of NP optimization problems". KTH NADA, Stockholm. Retrieved 21 June 2008.
- Dahlke, K. "NP-complete problems". Math Reference Project. Retrieved 21 June 2008.
Specific problems
- Friedman, E (2002). "Pearl puzzles are NP-complete". Stetson University, DeLand, Florida. Retrieved 21 June 2008.
- Grigoriev, A; Bodlaender, H L (2007). "Algorithms for graphs embeddable with few crossings per edge". Algorithmica. 49 (1): 1–11. CiteSeerX 10.1.1.61.3576. doi:10.1007/s00453-007-0010-x. MR 2344391.
{{cite journal}}: Invalid|ref=harv(help) - Hartung, S; Nichterlein, A (2012). How the World Computes. Lecture Notes in Computer Science. Vol. 7318. Springer, Berlin, Heidelberg. pp. 283–292. CiteSeerX 10.1.1.377.2077. doi:10.1007/978-3-642-30870-3_29. ISBN 978-3-642-30869-7.
- 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.
{{cite conference}}: Invalid|ref=harv(help); Unknown parameter|booktitle=ignored (|book-title=suggested) (help) - Kaye, Richard (2000). "Minesweeper is NP-complete". Mathematical Intelligencer. 22 (2): 9–15. doi:10.1007/BF03025367.
{{cite journal}}: Invalid|ref=harv(help) Further information available online at Richard Kaye's Minesweeper pages. - Kashiwabara, T.; Fujisawa, T. (1979). "NP-completeness of the problem of finding a minimum-clique-number interval graph containing a given graph as a subgraph". Proceedings. International Symposium on Circuits and Systems. pp. 657–660.
{{cite conference}}: Invalid|ref=harv(help) - Ohtsuki, Tatsuo; Mori, Hajimu; Kuh, Ernest S.; Kashiwabara, Toshinobu; Fujisawa, Toshio (1979). "One-dimensional logic gate assignment and interval graphs". IEEE Transactions on Circuits and Systems. 26 (9): 675–684. doi:10.1109/TCS.1979.1084695.
{{cite journal}}: Invalid|ref=harv(help) - Lengauer, Thomas (1981). "Black-white pebbles and graph separation". Acta Informatica. 16 (4): 465–475. doi:10.1007/BF00264496.
{{cite journal}}: Invalid|ref=harv(help) - Arnborg, Stefan; Corneil, Derek G.; Proskurowski, Andrzej (1987). "Complexity of finding embeddings in a k-tree". SIAM Journal on Algebraic and Discrete Methods. 8 (2): 277–284. doi:10.1137/0608024.
{{cite journal}}: Invalid|ref=harv(help) - 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.
{{cite conference}}: Unknown parameter|booktitle=ignored (|book-title=suggested) (help)