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¹
• 3-dimensional matching²³: SP1 
• Bandwidth problem⁴: GT40 
• Bipartite dimension⁵: GT18 
• Capacitated minimum spanning tree⁶: ND5 
• 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.⁷: ND25, ND27 
• Clique cover problem⁸⁹: GT17 
• Clique problem¹⁰¹¹: GT19 
• Complete coloring, a.k.a. achromatic number¹²: GT5 
• Cycle rank
• Degree-constrained spanning tree¹³: ND1 
• Domatic number¹⁴: GT3 
• Dominating set, a.k.a. domination number¹⁵: GT2 

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.¹⁶: ND2 

• Feedback vertex set¹⁷¹⁸: GT7 
• Feedback arc set¹⁹²⁰: GT8 
• Graph coloring²¹²²: GT4 
• Graph homomorphism problem²³: GT52 
• 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.²⁴: GT11, GT12, GT13, GT14, GT15, GT16, ND14 
• Grundy number of a directed graph.²⁵: GT56 
• Hamiltonian completion²⁶: GT34 
• Hamiltonian path problem, directed and undirected.²⁷²⁸: GT37, GT38, GT39 
• Induced subgraph isomorphism problem
• Graph intersection number²⁹: GT59 
• Longest path problem³⁰: ND29 
• Maximum bipartite subgraph or (especially with weighted edges) maximum cut.³¹³²: GT25, ND16 
• Maximum common subgraph isomorphism problem³³: GT49 
• Maximum independent set³⁴: GT20 
• Maximum Induced path³⁵: GT23 
• Minimum maximal independent set a.k.a. minimum independent dominating set³⁶

NP-complete special cases include the minimum maximal matching problem,³⁷: GT10  which is essentially equal to the edge dominating set problem (see above).

• Metric dimension of a graph³⁸: GT61 
• Metric k-center
• Minimum degree spanning tree
• Minimum k-cut
• Minimum k-spanning tree
• Minor testing (checking whether an input graph G {\displaystyle G} contains an input graph H {\displaystyle H} as a minor); the same holds with topological minors
• Steiner tree, or Minimum spanning tree for a subset of the vertices of a graph.³⁹ (The minimum spanning tree for an entire graph is solvable in polynomial time.)
• Modularity maximization⁴⁰
• Monochromatic triangle⁴¹: GT6 
• Pathwidth,⁴² or, equivalently, interval thickness, and vertex separation number⁴³
• Rank coloring
• k-Chinese postman
• Shortest total path length spanning tree⁴⁴: ND3 
• Slope number two testing⁴⁵
• Recognizing string graphs⁴⁶
• Subgraph isomorphism problem⁴⁷: GT48 
• Treewidth⁴⁸
• Testing whether a tree may be represented as Euclidean minimum spanning tree
• Vertex cover⁴⁹⁵⁰: GT1 

Mathematical programming

• 3-partition problem⁵¹: SP15 
• Bin packing problem⁵²: SR1 
• Bottleneck traveling salesman⁵³: ND24 
• Uncapacitated facility location problem
• Flow Shop Scheduling Problem
• Generalized assignment problem
• 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⁵⁴⁵⁵: MP1 
• Some problems related to Job-shop scheduling
• Knapsack problem, quadratic knapsack problem, and several variants⁵⁶⁵⁷: MP9 
• Some problems related to Multiprocessor scheduling
• Numerical 3-dimensional matching⁵⁸: SP16 
• Open-shop scheduling
• Partition problem⁵⁹⁶⁰: SP12 
• Quadratic assignment problem⁶¹: ND43 
• Quadratic programming (NP-hard in some cases, P if convex)
• Subset sum problem⁶²: SP13 
• 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.⁶³: ND22, ND23 

Formal languages and string processing

• Closest string⁶⁴
• Longest common subsequence problem over multiple sequences⁶⁵: SR10 
• The bounded variant of the Post correspondence problem⁶⁶: SR11 
• Shortest common supersequence over multiple sequences⁶⁷: SR8 
• Extension of the string-to-string correction problem⁶⁸⁶⁹: SR8 

Games and puzzles

• Bag (Corral)⁷⁰
• Battleship
• Bulls and Cows, marketed as Master Mind: certain optimisation problems but not the game itself.
• Edge-matching puzzles
• Fillomino⁷¹
• (Generalized) FreeCell⁷²
• Goishi Hiroi
• Hashiwokakero⁷³
• Heyawake⁷⁴
• (Generalized) Instant Insanity⁷⁵: GP15 
• Kakuro (Cross Sums)⁷⁶
• Kingdomino⁷⁷
• Kuromasu (also known as Kurodoko)⁷⁸
• LaserTank⁷⁹
• Lemmings (with a polynomial time limit)⁸⁰
• Light Up⁸¹
• Mahjong solitaire (with looking below tiles)
• Masyu⁸²
• Minesweeper Consistency Problem⁸³ (but see Scott, Stege, & van Rooij⁸⁴)
• Nonograms
• Numberlink
• Nurikabe⁸⁵
• (Generalized) Pandemic⁸⁶
• Peg solitaire
• n-Queens completion
• Optimal solution for the N×N×N Rubik's Cube⁸⁷
• SameGame
• Shakashaka
• Slither Link on a variety of grids⁸⁸⁸⁹⁹⁰
• (Generalized) Sudoku⁹¹⁹²
• Tatamibari
• Tentai Show
• Problems related to Tetris⁹³
• Verbal arithmetic

Other

• Berth allocation problem⁹⁴
• Betweenness
• Assembling an optimal Bitcoin block.⁹⁵
• Boolean satisfiability problem (SAT).⁹⁶⁹⁷: 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.⁹⁸: p. 48 
• Circuit satisfiability problem
• Conjunctive Boolean query⁹⁹: SR31 
• Cyclic ordering¹⁰⁰
• Exact cover problem. Remains NP-complete for 3-sets. Solvable in polynomial time for 2-sets (this is a matching).¹⁰¹¹⁰²: SP2 
• Finding the global minimum solution of a Hartree-Fock problem¹⁰³
• Upward planarity testing¹⁰⁴
• Hospitals-and-residents problem with couples
• Knot genus¹⁰⁵
• Latin square completion (the problem of determining if a partially filled square can be completed)
• Maximum 2-satisfiability¹⁰⁶: LO5 
• Maximum volume submatrix – Problem of selecting the best conditioned subset of a larger m × n {\displaystyle m\times n} matrix. This class of problem is associated with Rank revealing QR factorizations and D optimal experimental design.¹⁰⁷
• Minimal addition chains for sequences.¹⁰⁸ The complexity of minimal addition chains for individual numbers is unknown.¹⁰⁹
• Modal logic S5-Satisfiability
• Pancake sorting distance problem for strings¹¹⁰
• Solubility of two-variable quadratic polynomials over the integers.¹¹¹ Given positive integers A , B , C {\displaystyle \textstyle A,B,C} , decide existence of positive integers x , y {\displaystyle x,y} such that A x 2 + B y − C = 0 {\displaystyle Ax^{2}+By-C=0}
• By the same article¹¹² existence of bounded modular square roots with arbitrarily composite modulus. Given positive integers A , B , C ≥ 0 {\displaystyle \textstyle A,B,C\geq 0} , decide existence of an integer x ∈ [ 0 , C ] {\displaystyle x\in [0,C]} such that x 2 ≡ A mod B {\displaystyle x^{2}\equiv A{\bmod {B}}} . The problem remains NP-complete even if a prime factorization of B {\displaystyle B} is provided.
• Serializability of database histories¹¹³: SR33 
• Set cover (also called "minimum cover" problem). This is equivalent, by transposing the incidence matrix, to the hitting set problem.¹¹⁴¹¹⁵: SP5, SP8 
• Set packing¹¹⁶¹¹⁷: SP3 
• Set splitting problem¹¹⁸: SP4 
• Scheduling to minimize weighted completion time
• Block Sorting¹¹⁹ (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.¹²⁰: ND13 
• Three-dimensional Ising model¹²¹

See also

• Existential theory of the reals § Complete problems
• Karp's 21 NP-complete problems
• List of PSPACE-complete problems
• Reduction (complexity)

Notes

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.
• Karp, Richard M. (1972). "Reducibility among combinatorial problems". In Miller, Raymond E.; Thatcher, James W. (eds.). Complexity of Computer Computations. Plenum. pp. 85–103.
• 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. Archived from the original on 4 September 2006. 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. S2CID 8174422.
• Hartung, S; Nichterlein, A (2012). "NP-Hardness and Fixed-Parameter Tractability of Realizing Degree Sequences with Directed Acyclic Graphs". 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. S2CID 6112925.
• Holzer, Markus; Ruepp, Oliver (2007). "The Troubles of Interior Design–A Complexity Analysis of the Game Heyawake" (PDF). 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.
• Kaye, Richard (2000). "Minesweeper is NP-complete". Mathematical Intelligencer. 22 (2): 9–15. doi:10.1007/BF03025367. S2CID 122435790. 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.
• 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.
• Lengauer, Thomas (1981). "Black-white pebbles and graph separation". Acta Informatica. 16 (4): 465–475. doi:10.1007/BF00264496. S2CID 19415148.
• 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.
• 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

• A compendium of NP optimization problems
• Graph of NP-complete Problems

References

1. Grigoriev & Bodlaender (2007). - 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. S2CID 8174422. https://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.61.3576 ↩

2. Karp (1972) - Karp, Richard M. (1972). "Reducibility among combinatorial problems". In Miller, Raymond E.; Thatcher, James W. (eds.). Complexity of Computer Computations. Plenum. pp. 85–103. ↩

3. Garey & Johnson (1979) - 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. https://mathscinet.ams.org/mathscinet-getitem?mr=0519066 ↩

4. Garey & Johnson (1979) - 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. https://mathscinet.ams.org/mathscinet-getitem?mr=0519066 ↩

5. Garey & Johnson (1979) - 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. https://mathscinet.ams.org/mathscinet-getitem?mr=0519066 ↩

6. Garey & Johnson (1979) - 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. https://mathscinet.ams.org/mathscinet-getitem?mr=0519066 ↩

7. Garey & Johnson (1979) - 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. https://mathscinet.ams.org/mathscinet-getitem?mr=0519066 ↩

8. Karp (1972) - Karp, Richard M. (1972). "Reducibility among combinatorial problems". In Miller, Raymond E.; Thatcher, James W. (eds.). Complexity of Computer Computations. Plenum. pp. 85–103. ↩

9. Garey & Johnson (1979) - 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. https://mathscinet.ams.org/mathscinet-getitem?mr=0519066 ↩

10. Karp (1972) - Karp, Richard M. (1972). "Reducibility among combinatorial problems". In Miller, Raymond E.; Thatcher, James W. (eds.). Complexity of Computer Computations. Plenum. pp. 85–103. ↩

11. Garey & Johnson (1979) - 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. https://mathscinet.ams.org/mathscinet-getitem?mr=0519066 ↩

12. Garey & Johnson (1979) - 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. https://mathscinet.ams.org/mathscinet-getitem?mr=0519066 ↩

13. Garey & Johnson (1979) - 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. https://mathscinet.ams.org/mathscinet-getitem?mr=0519066 ↩

14. Garey & Johnson (1979) - 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. https://mathscinet.ams.org/mathscinet-getitem?mr=0519066 ↩

15. Garey & Johnson (1979) - 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. https://mathscinet.ams.org/mathscinet-getitem?mr=0519066 ↩

16. Garey & Johnson (1979) - 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. https://mathscinet.ams.org/mathscinet-getitem?mr=0519066 ↩

17. Karp (1972) - Karp, Richard M. (1972). "Reducibility among combinatorial problems". In Miller, Raymond E.; Thatcher, James W. (eds.). Complexity of Computer Computations. Plenum. pp. 85–103. ↩

18. Garey & Johnson (1979) - 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. https://mathscinet.ams.org/mathscinet-getitem?mr=0519066 ↩

19. Karp (1972) - Karp, Richard M. (1972). "Reducibility among combinatorial problems". In Miller, Raymond E.; Thatcher, James W. (eds.). Complexity of Computer Computations. Plenum. pp. 85–103. ↩

20. Garey & Johnson (1979) - 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. https://mathscinet.ams.org/mathscinet-getitem?mr=0519066 ↩

21. Karp (1972) - Karp, Richard M. (1972). "Reducibility among combinatorial problems". In Miller, Raymond E.; Thatcher, James W. (eds.). Complexity of Computer Computations. Plenum. pp. 85–103. ↩

22. Garey & Johnson (1979) - 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. https://mathscinet.ams.org/mathscinet-getitem?mr=0519066 ↩

23. Garey & Johnson (1979) - 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. https://mathscinet.ams.org/mathscinet-getitem?mr=0519066 ↩

24. Garey & Johnson (1979) - 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. https://mathscinet.ams.org/mathscinet-getitem?mr=0519066 ↩

25. Garey & Johnson (1979) - 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. https://mathscinet.ams.org/mathscinet-getitem?mr=0519066 ↩

26. Garey & Johnson (1979) - 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. https://mathscinet.ams.org/mathscinet-getitem?mr=0519066 ↩

27. Karp (1972) - Karp, Richard M. (1972). "Reducibility among combinatorial problems". In Miller, Raymond E.; Thatcher, James W. (eds.). Complexity of Computer Computations. Plenum. pp. 85–103. ↩

28. Garey & Johnson (1979) - 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. https://mathscinet.ams.org/mathscinet-getitem?mr=0519066 ↩

29. Garey & Johnson (1979) - 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. https://mathscinet.ams.org/mathscinet-getitem?mr=0519066 ↩

30. Garey & Johnson (1979) - 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. https://mathscinet.ams.org/mathscinet-getitem?mr=0519066 ↩

31. Karp (1972) - Karp, Richard M. (1972). "Reducibility among combinatorial problems". In Miller, Raymond E.; Thatcher, James W. (eds.). Complexity of Computer Computations. Plenum. pp. 85–103. ↩

32. Garey & Johnson (1979) - 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. https://mathscinet.ams.org/mathscinet-getitem?mr=0519066 ↩

33. Garey & Johnson (1979) - 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. https://mathscinet.ams.org/mathscinet-getitem?mr=0519066 ↩

34. Garey & Johnson (1979) - 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. https://mathscinet.ams.org/mathscinet-getitem?mr=0519066 ↩

35. Garey & Johnson (1979) - 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. https://mathscinet.ams.org/mathscinet-getitem?mr=0519066 ↩

36. Minimum Independent Dominating Set http://www.csc.kth.se/~viggo/wwwcompendium/node14.html ↩

37. Garey & Johnson (1979) - 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. https://mathscinet.ams.org/mathscinet-getitem?mr=0519066 ↩

38. Garey & Johnson (1979) - 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. https://mathscinet.ams.org/mathscinet-getitem?mr=0519066 ↩

39. Karp (1972) - Karp, Richard M. (1972). "Reducibility among combinatorial problems". In Miller, Raymond E.; Thatcher, James W. (eds.). Complexity of Computer Computations. Plenum. pp. 85–103. ↩

40. 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 /wiki/Ulrik_Brandes ↩

41. Garey & Johnson (1979) - 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. https://mathscinet.ams.org/mathscinet-getitem?mr=0519066 ↩

42. Arnborg, Corneil & Proskurowski (1987) - 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. https://doi.org/10.1137%2F0608024 ↩

43. Kashiwabara & Fujisawa (1979); Ohtsuki et al. (1979); Lengauer (1981). - 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. ↩

44. Garey & Johnson (1979) - 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. https://mathscinet.ams.org/mathscinet-getitem?mr=0519066 ↩

45. 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. 978-3-540-58950-1 ↩

46. 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. https://doi.org/10.1016%2FS0022-0000%2803%2900045-X ↩

47. Garey & Johnson (1979) - 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. https://mathscinet.ams.org/mathscinet-getitem?mr=0519066 ↩

48. Arnborg, Corneil & Proskurowski (1987) - 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. https://doi.org/10.1137%2F0608024 ↩

49. Karp (1972) - Karp, Richard M. (1972). "Reducibility among combinatorial problems". In Miller, Raymond E.; Thatcher, James W. (eds.). Complexity of Computer Computations. Plenum. pp. 85–103. ↩

50. Garey & Johnson (1979) - 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. https://mathscinet.ams.org/mathscinet-getitem?mr=0519066 ↩

51. Garey & Johnson (1979) - 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. https://mathscinet.ams.org/mathscinet-getitem?mr=0519066 ↩

52. Garey & Johnson (1979) - 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. https://mathscinet.ams.org/mathscinet-getitem?mr=0519066 ↩

53. Garey & Johnson (1979) - 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. https://mathscinet.ams.org/mathscinet-getitem?mr=0519066 ↩

54. Karp (1972) - Karp, Richard M. (1972). "Reducibility among combinatorial problems". In Miller, Raymond E.; Thatcher, James W. (eds.). Complexity of Computer Computations. Plenum. pp. 85–103. ↩

55. Garey & Johnson (1979) - 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. https://mathscinet.ams.org/mathscinet-getitem?mr=0519066 ↩

56. Karp (1972) - Karp, Richard M. (1972). "Reducibility among combinatorial problems". In Miller, Raymond E.; Thatcher, James W. (eds.). Complexity of Computer Computations. Plenum. pp. 85–103. ↩

57. Garey & Johnson (1979) - 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. https://mathscinet.ams.org/mathscinet-getitem?mr=0519066 ↩

58. Garey & Johnson (1979) - 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. https://mathscinet.ams.org/mathscinet-getitem?mr=0519066 ↩

59. Karp (1972) - Karp, Richard M. (1972). "Reducibility among combinatorial problems". In Miller, Raymond E.; Thatcher, James W. (eds.). Complexity of Computer Computations. Plenum. pp. 85–103. ↩

60. Garey & Johnson (1979) - 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. https://mathscinet.ams.org/mathscinet-getitem?mr=0519066 ↩

61. Garey & Johnson (1979) - 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. https://mathscinet.ams.org/mathscinet-getitem?mr=0519066 ↩

62. Garey & Johnson (1979) - 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. https://mathscinet.ams.org/mathscinet-getitem?mr=0519066 ↩

63. Garey & Johnson (1979) - 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. https://mathscinet.ams.org/mathscinet-getitem?mr=0519066 ↩

64. 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 /wiki/Doi_(identifier) ↩

65. Garey & Johnson (1979) - 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. https://mathscinet.ams.org/mathscinet-getitem?mr=0519066 ↩

66. Garey & Johnson (1979) - 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. https://mathscinet.ams.org/mathscinet-getitem?mr=0519066 ↩

67. Garey & Johnson (1979) - 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. https://mathscinet.ams.org/mathscinet-getitem?mr=0519066 ↩

68. 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. S2CID 18705107. 9781450374194 ↩

69. Garey & Johnson (1979) - 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. https://mathscinet.ams.org/mathscinet-getitem?mr=0519066 ↩

70. Friedman, Erich. "Corral Puzzles are NP-complete" (PDF). Retrieved 17 August 2021. https://erich-friedman.github.io/papers/corral.pdf ↩

71. Yato, Takauki (2003). Complexity and Completeness of Finding Another Solution and its Application to Puzzles. CiteSeerX 10.1.1.103.8380. /wiki/CiteSeerX_(identifier) ↩

72. Malte Helmert, Complexity results for standard benchmark domains in planning, Artificial Intelligence 143(2):219-262, 2003. ↩

73. "HASHIWOKAKERO Is NP-Complete". http://www.cs.au.dk/~koda/hashiwokakero ↩

74. Holzer & Ruepp (2007) - Holzer, Markus; Ruepp, Oliver (2007). "The Troubles of Interior Design–A Complexity Analysis of the Game Heyawake" (PDF). 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. https://mediatum.ub.tum.de/doc/1289953/document.pdf ↩

75. Garey & Johnson (1979) - 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. https://mathscinet.ams.org/mathscinet-getitem?mr=0519066 ↩

76. Takahiro, Seta (5 February 2002). "The complexities of puzzles, cross sum and their another solution problems (ASP)" (PDF). Retrieved 18 November 2018. http://www-imai.is.s.u-tokyo.ac.jp/~seta/paper/senior_thesis/seniorthesis.pdf ↩

77. 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. S2CID 218552723. https://doi.org/10.1016%2Fj.tcs.2020.04.007 ↩

78. 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. Archived from the original (PDF) on 12 February 2020. https://web.archive.org/web/20200212021124/https://pdfs.semanticscholar.org/4971/aa310e07aaa07c1ba7299f519b39ba5c5195.pdf ↩

79. Alexandersson, Per; Restadh, Petter (2020). "LaserTank is NP-Complete". Mathematical Aspects of Computer and Information Sciences. Lecture Notes in Computer Science. Vol. 11989. Springer International Publishing. pp. 333–338. arXiv:1908.05966. doi:10.1007/978-3-030-43120-4_26. ISBN 978-3-030-43119-8. S2CID 201058355. 978-3-030-43119-8 ↩

80. Cormode, Graham (2004). The hardness of the lemmings game, or Oh no, more NP-completeness proofs (PDF). http://dimacs.rutgers.edu/~graham/pubs/papers/cormodelemmings.pdf ↩

81. Light Up is NP-Complete https://web.archive.org/web/20080308132136/http://www.cs.umass.edu/~mcphailb/papers/2005lightup.pdf ↩

82. Friedman, Erich (27 March 2012). "Pearl Puzzles are NP-complete". Archived from the original on 4 February 2012. https://web.archive.org/web/20120204150006/http://www2.stetson.edu/~efriedma/papers/pearl/pearl.html ↩

83. Kaye (2000) - Kaye, Richard (2000). "Minesweeper is NP-complete". Mathematical Intelligencer. 22 (2): 9–15. doi:10.1007/BF03025367. S2CID 122435790. https://doi.org/10.1007%2FBF03025367 ↩

84. 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. ↩

85. Holzer, Markus; Klein, Andreas; Kutrib, Martin; Ruepp, Oliver (2011). "Computational Complexity of NURIKABE". Fundamenta Informaticae. 110 (1–4): 159–174. doi:10.3233/FI-2011-534. /wiki/Doi_(identifier) ↩

86. 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. https://doi.org/10.2197%2Fipsjjip.20.723 ↩

87. 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. /wiki/Doi_(identifier) ↩

88. Sato, Takayuki; Seta, Takahiro (1987). Complexity and Completeness of Finding Another Solution and Its Application to Puzzles (PDF). International Symposium on Algorithms (SIGAL 1987). http://www-imai.is.s.u-tokyo.ac.jp/~yato/data2/SIGAL87-2.pdf ↩

89. 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/ ↩

90. 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. https://doi.org/10.2197%2Fipsjjip.20.709 ↩

91. Sato, Takayuki; Seta, Takahiro (1987). Complexity and Completeness of Finding Another Solution and Its Application to Puzzles (PDF). International Symposium on Algorithms (SIGAL 1987). http://www-imai.is.s.u-tokyo.ac.jp/~yato/data2/SIGAL87-2.pdf ↩

92. A SURVEY OF NP-COMPLETE PUZZLES, Section 23; Graham Kendall, Andrew Parkes, Kristian Spoerer; March 2008. (icga2008.pdf) https://www.cs.wmich.edu/elise/courses/cs431/icga2008.pdf ↩

93. 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. http://erikdemaine.org/papers/Tetris_COCOON2003/paper.pdf ↩

94. 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 /wiki/Doi_(identifier) ↩

95. J. Bonneau, "Bitcoin mining is NP-hard" https://freedom-to-tinker.com/blog/jbonneau/bitcoin-mining-is-np-hard/ ↩

96. Karp (1972) - Karp, Richard M. (1972). "Reducibility among combinatorial problems". In Miller, Raymond E.; Thatcher, James W. (eds.). Complexity of Computer Computations. Plenum. pp. 85–103. ↩

97. Garey & Johnson (1979) - 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. https://mathscinet.ams.org/mathscinet-getitem?mr=0519066 ↩

98. Garey & Johnson (1979) - 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. https://mathscinet.ams.org/mathscinet-getitem?mr=0519066 ↩

99. Garey & Johnson (1979) - 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. https://mathscinet.ams.org/mathscinet-getitem?mr=0519066 ↩

100. 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. https://doi.org/10.1016%2F0304-3975%2877%2990005-6 ↩

101. Karp (1972) - Karp, Richard M. (1972). "Reducibility among combinatorial problems". In Miller, Raymond E.; Thatcher, James W. (eds.). Complexity of Computer Computations. Plenum. pp. 85–103. ↩

102. Garey & Johnson (1979) - 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. https://mathscinet.ams.org/mathscinet-getitem?mr=0519066 ↩

103. Whitfield, James Daniel; Love, Peter John; Aspuru-Guzik, Alán (2013). "Computational complexity in electronic structure". Phys. Chem. Chem. Phys. 15 (2): 397–411. arXiv:1208.3334. Bibcode:2013PCCP...15..397W. doi:10.1039/C2CP42695A. PMID 23172634. S2CID 12351374. https://doi.org/10.1039/C2CP42695A ↩

104. 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. 978-3-540-58950-1 ↩

105. Agol, Ian; Hass, Joel; Thurston, William (19 May 2002). "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. arXiv:math/0205057. doi:10.1145/509907.510016. ISBN 978-1-58113-495-7. S2CID 10401375. 978-1-58113-495-7 ↩

106. Garey & Johnson (1979) - 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. https://mathscinet.ams.org/mathscinet-getitem?mr=0519066 ↩

107. Çivril, Ali; Magdon-Ismail, Malik (2009), "On selecting a maximum volume sub-matrix of a matrix and related problems" (PDF), Theoretical Computer Science, 410 (47–49): 4801–4811, doi:10.1016/j.tcs.2009.06.018, MR 2583677, archived from the original (PDF) on 3 February 2015 https://web.archive.org/web/20150203193923/http://www.meliksah.edu.tr/acivril/max-vol-original.pdf ↩

108. Peter Downey, Benton Leong, and Ravi Sethi. "Computing Sequences with Addition Chains" SIAM J. Comput., 10(3), 638–646, 1981 ↩

109. D. J. Bernstein, "Pippinger's exponentiation algorithm" (draft) http://cr.yp.to/papers/pippenger.pdf ↩

110. 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. /wiki/ArXiv_(identifier) ↩

111. 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. S2CID 18885088. 9781450374149 ↩

112. 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. S2CID 18885088. 9781450374149 ↩

113. Garey & Johnson (1979) - 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. https://mathscinet.ams.org/mathscinet-getitem?mr=0519066 ↩

114. Karp (1972) - Karp, Richard M. (1972). "Reducibility among combinatorial problems". In Miller, Raymond E.; Thatcher, James W. (eds.). Complexity of Computer Computations. Plenum. pp. 85–103. ↩

115. Garey & Johnson (1979) - 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. https://mathscinet.ams.org/mathscinet-getitem?mr=0519066 ↩

116. Karp (1972) - Karp, Richard M. (1972). "Reducibility among combinatorial problems". In Miller, Raymond E.; Thatcher, James W. (eds.). Complexity of Computer Computations. Plenum. pp. 85–103. ↩

117. Garey & Johnson (1979) - 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. https://mathscinet.ams.org/mathscinet-getitem?mr=0519066 ↩

118. Garey & Johnson (1979) - 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. https://mathscinet.ams.org/mathscinet-getitem?mr=0519066 ↩

119. Bein, W. W.; Larmore, L. L.; Latifi, S.; Sudborough, I. H. (1 January 2002). "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. S2CID 32222403. 978-0-7695-1579-3 ↩

120. Garey & Johnson (1979) - 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. https://mathscinet.ams.org/mathscinet-getitem?mr=0519066 ↩

121. Barry Arthur Cipra, "The Ising Model Is NP-Complete", SIAM News, Vol 33, No 6. /wiki/Barry_Arthur_Cipra ↩