Category:NP-complete problems

M

• Minesweeper (video game)‎ (4 P)

N

• Nonograms‎ (1 C, 12 P)
• Number partitioning‎ (12 P)

S

• SAT solvers‎ (7 P)
• SMT solvers‎ (2 P)
• Strongly NP-complete problems‎ (1 C, 6 P)
• Sudoku‎ (3 C, 17 P, 3 F)

T

• Tetris‎ (57 P, 1 F)

W

• Weakly NP-complete problems‎ (1 C, 5 P)

• NP-completeness

*

• Karp's 21 NP-complete problems
• List of NP-complete problems

0–9

• 3-dimensional matching
• 15 puzzle

B

• Battleship (puzzle)
• Betweenness
• Bipartite dimension
• Boolean satisfiability problem

C

• Chinese postman problem
• Circuit satisfiability problem
• Clique cover
• Clique problem

D

• Degree-constrained spanning tree
• Domatic number
• Dominating set

E

• Edge dominating set
• Exact cover

F

• Feedback arc set
• Feedback vertex set

G

• Generalized assignment problem
• Graph coloring
• Graph partition

H

• Hamiltonian completion
• Hamiltonian path
• Hamiltonian cycle polynomial
• Hamiltonian path problem
• Hashiwokakero
• Hitori
• Hitting set

I

• Independent set (graph theory)
• Induced subgraph isomorphism problem
• Instant Insanity

K

• Kakuro
• Knapsack problem

L

• Light Up (puzzle)
• Longest common subsequence
• Longest path problem

M

• Mastermind (board game)
• Masyu
• Maximum common induced subgraph
• Maximum coverage problem
• Maximum cut
• Minesweeper (video game)
• Minimum k-cut
• Minimum routing cost spanning tree
• Monochromatic triangle

N

• Nonogram
• Not-all-equal 3-satisfiability
• Nurikabe (puzzle)

P

• Planar SAT

Q

• Quadratic knapsack problem
• Quadratic residue
• Quadrel

R

• Radio coloring

S

• SameGame
• (SAT, ε-UNSAT)
• Satisfiability modulo theories
• Set cover problem
• Set packing
• Set splitting problem
• Set TSP problem
• Shakashaka
• Shortest common supersequence problem
• Slitherlink
• Steiner tree problem
• Subgraph isomorphism problem
• Sudoku

T

• Tentai Show
• Tetris
• Token reconfiguration
• Traveling purchaser problem
• Travelling salesman problem

U

• Unit disk graph

V

• Vehicle routing problem
• Vertex cover
• Vertex cycle cover

Z

• Zero-weight cycle problem