List of NP-complete problems

Graphs and hypergraphs

• 1-planarity
• 3-dimensional matching
• Bandwidth problem
• Bipartite dimension
• Capacitated minimum spanning tree
• Route inspection problem for mixed graphs. The program is solvable in polynomial time if the graph has all undirected or all directed edges. Variants include the rural postman problem.
• Clique cover problem
• Clique problem
• Complete coloring, a.k.a. achromatic number
• Cycle rank
• Degree-constrained spanning tree
• Domatic number
• Dominating set, a.k.a. domination number
• Feedback vertex set
• Feedback arc set
• Graph coloring
• Graph homomorphism problem
• Graph partition into subgraphs of specific types 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.
• Grundy number of a directed graph.
• Hamiltonian completion
• Hamiltonian path problem, directed and undirected.
• Induced subgraph isomorphism problem
• Graph intersection number
• Longest path problem
• Maximum bipartite subgraph or maximum cut.
• Maximum common subgraph isomorphism problem
• Maximum independent set
• Maximum Induced path
• Minimum maximal independent set a.k.a. minimum independent dominating set
• Metric dimension of a graph
• Metric k-center
• Minimum degree spanning tree
• Minimum k-cut
• Minimum k-spanning tree
• Minor testing ; the same holds with topological minors
• Steiner tree, or Minimum spanning tree for a subset of the vertices of a graph.
• Modularity maximization
• Monochromatic triangle
• Pathwidth, or, equivalently, interval thickness, and vertex separation number
• Rank coloring
• k-Chinese postman
• Shortest total path length spanning tree
• Slope number two testing
• Recognizing string graphs
• Subgraph isomorphism problem
• Treewidth
• Testing whether a tree may be represented as Euclidean minimum spanning tree
• Vertex cover

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
• 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 Euclidean metric.

Formal languages and string processing

• Closest string
• Longest common subsequence problem over multiple sequences
• The bounded variant of the Post correspondence problem
• Shortest common supersequence over multiple sequences
• Extension of the string-to-string correction problem

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
• FreeCell
• Goishi Hiroi
• Hashiwokakero
• Heyawake
• Instant Insanity
• Kakuro (Cross Sums)
• Kingdomino
• Kuromasu
• LaserTank
• Lemmings
• Light Up
• Mahjong solitaire
• Masyu
• Minesweeper Consistency Problem
• Nonograms
• Numberlink
• Nurikabe
• Pandemic
• Peg solitaire
• n-Queens completion
• Optimal solution for the Rubik's Cube
• SameGame
• Shakashaka
• Slither Link on a variety of grids
• Sudoku
• Tatamibari
• Tentai Show
• Problems related to Tetris
• Verbal arithmetic

Other

• Berth allocation problem
• Betweenness
• Assembling an optimal Bitcoin block.
• Boolean satisfiability problem. There are many variations that are also NP-complete. An important variant is where each clause has exactly three literals, 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.
• Finding the global minimum solution of a Hartree-Fock problem
• Upward planarity testing
• Hospitals-and-residents problem with couples
• Knot genus
• Latin square completion
• Maximum 2-satisfiability
• Maximum volume submatrix – Problem of selecting the best conditioned subset of a larger 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, decide existence of positive integers such that
• By the same article existence of bounded modular square roots with arbitrarily composite modulus. Given positive integers, decide existence of an integer such that. The problem remains NP-complete even if a prime factorization of is provided.
• Serializability of database histories
• Set cover. 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
• 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 Euclidean metric.
• Three-dimensional Ising model