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 .

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
  • Bandwidth problem

::NP-complete special cases include the minimum maximal matching problem,

  • Monochromatic triangle
  • Rank coloring
  • k-Chinese postman
  • Shortest total path length spanning tree
  • Recognizing string graphs
  • Subgraph isomorphism problem
  • Testing whether a tree may be represented as Euclidean minimum spanning tree
  • Vertex cover
  • Longest common subsequence problem over multiple sequences
  • 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
  • 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 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).
  • Exact cover problem. Remains NP-complete for 3-sets. Solvable in polynomial time for 2-sets (this is a matching).
  • Upward planarity testing
  • Latin square completion (the problem of determining if a partially filled square can be completed)
  • Maximum 2-satisfiability
  • 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 <math>\textstyle A,B,C</math>, decide existence of positive integers <math>x,y</math> such that <math>Ax^2+By-C=0</math>
  • By the same article (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.

<!--

Propositional logic problems, in particular satisfiability problems and their variants, are of particular practical interest because many practical problems can be solved by expressing them as satisfiability problems, and then using efficient SAT solvers to obtain an exact solution quickly.

-->

See also

  • Karp's 21 NP-complete problems
  • List of PSPACE-complete problems
  • Reduction (complexity)

Notes

References

General

  • . This book is a classic, developing the theory, then cataloguing many NP-Complete problems.

Specific problems

  • Further information available online at Richard Kaye's Minesweeper pages .
  • A compendium of NP optimization problems
  • Graph of NP-complete Problems