Category:NP-complete problems

• NP-completeness (computing)

*

• Karp's 21 NP-complete problems (computing)
• List of NP-complete problems (computing)

1

• 15 puzzle (computing)

3

• 3-dimensional matching (computing)

B

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

C

• Circuit satisfiability problem (computing)
• Clique cover (computing)
• Clique problem (computing)
• Crossword (computing)

D

• Degree-constrained spanning tree (computing)
• Domatic number (computing)
• Dominating set (computing)

E

• Edge dominating set (computing)
• Exact cover (computing)

F

• Feedback arc set (computing)
• Feedback vertex set (computing)

G

• Generalized assignment problem (computing)
• Graph coloring (computing)
• Graph partition (computing)

H

• Hamiltonian completion (computing)
• Hamiltonian path (computing)
• Hamiltonian cycle polynomial (computing)
• Hamiltonian path problem (computing)
• Hashiwokakero (computing)
• Hatena Satena (computing)
• Hitori (computing)
• Hitting set (computing)

I

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

K

• Kakuro (computing)
• Knapsack problem (computing)

L

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

M

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

N

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

P

• Partition problem (computing)
• Planar SAT (computing)

Q

• Quadratic knapsack problem (computing)
• Quadratic residue (computing)
• Quadrel (computing)

R

• Radio coloring (computing)
• Route inspection problem (computing)

S

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

T

• Tetris (computing)
• Token reconfiguration (computing)
• Traveling purchaser problem (computing)
• Travelling salesman problem (computing)

U

• Unit disk graph (computing)

V

• Vehicle rescheduling problem (computing)
• Vehicle routing problem (computing)
• Vertex cover (computing)
• Vertex cycle cover (computing)

W

• Wiener connector (computing)

Z

• Zero-weight cycle problem (computing)