Category:NP-complete problems

M

• ► Minesweeper (video game)‎ (3 P)

N

• ► Nonograms‎ (11 P)

S

• ► SAT solvers‎ (6 P)
• ► SMT solvers‎ (1 P)
• ► Strongly NP-complete problems‎ (1 C, 5 P)
• ► Sudoku‎ (2 C, 22 P, 5 F)

T

• ► Tetris‎ (43 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

• Circuit satisfiability problem
• Clique cover
• Clique problem
• Crossword

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 path problem
• Hashiwokakero
• Hitori
• Hitting set

I

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

K

• Kakuro
• Knapsack problem

L

• L(h, k)-coloring
• Light Up (puzzle)
• Longest common subsequence problem
• Longest path problem

M

• Mastermind (board game)
• Masyu
• Maximum common induced subgraph
• Maximum coverage problem
• Maximum cut
• Minesweeper (video game)
• Minimum k-cut
• Monochromatic triangle
• Multi-trials technique

N

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

P

• Partition problem

Q

• Quadratic knapsack problem
• Quadratic residue
• Quadrel

R

• Radio coloring
• Route inspection problem

S

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

T

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

U

• Unit disk graph

V

• Vehicle rescheduling problem
• Vehicle routing problem
• Vertex cover
• Vertex cycle cover

W

• Wiener connector