List of NP-complete problems

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 • Minimum Wiener connector problem ==Mathematical programming==

• 3-partition problem • Bin packing problem • Bottleneck traveling salesman • 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 • Some problems related to job-shop scheduling • Knapsack problem, quadratic knapsack problem, and several variants • Some problems related to multiprocessor scheduling • Numerical 3-dimensional matching • Open-shop scheduling • Partition problem • Quadratic assignment problem • Quadratic programming (NP-hard in some cases, P if convex) • Subset sum problem • 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. ==Formal languages and string processing==

• Closest string • Longest common subsequence problem over multiple sequences ==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 • 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 \textstyle A,B,C, decide existence of positive integers x,y such that Ax^2+By-C=0 • 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. ==See also==