This is a list of some of the more commonly known problems that are NP-complete when expressed as decision problems. As there are thousands 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).

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.

NP-complete special cases include the minimum maximal matching problem, 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
  • Betweenness
  • Assembling an optimal Bitcoin block.
  • Boolean satisfiability problem (SAT). 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.
  • Circuit satisfiability problem
  • Conjunctive Boolean query
  • Cyclic ordering
  • Exact cover problem. Remains NP-complete for 3-sets. Solvable in polynomial time for 2-sets (this is a matching).
  • 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
  • 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
  • Set cover (also called "minimum cover" problem). This is equivalent, by transposing the incidence matrix, to the hitting set problem.
  • Set packing
  • Set splitting problem
  • 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.
  • Three-dimensional Ising model

See also

Notes

General

Specific problems

  • Friedman, E (2002). . Stetson University, DeLand, Florida.
  • Grigoriev, A; Bodlaender, H L (2007). "Algorithms for graphs embeddable with few crossings per edge". Algorithmica. 49 (1): 1–11. CiteSeerX . doi:. MR . S2CID .
  • 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 . doi:. ISBN 978-3-642-30869-7. S2CID .
  • Holzer, Markus; Ruepp, Oliver (2007). (PDF). Proceedings, 4th International Conference on Fun with Algorithms, LNCS 4475. Springer, Berlin/Heidelberg. pp. 198–212. doi:. ISBN 978-3-540-72913-6.
  • Kaye, Richard (2000). "Minesweeper is NP-complete". Mathematical Intelligencer. 22 (2): 9–15. doi:. S2CID . Further information available online at .
  • 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:.
  • Lengauer, Thomas (1981). "Black-white pebbles and graph separation". Acta Informatica. 16 (4): 465–475. doi:. S2CID .
  • 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:.
  • 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