Category:NP-complete problems

N

• ► Nonograms‎ (7 P)

S

• ► SAT solvers‎ (4 P)
• ► SMT solvers‎ (2 P)

S cont.

• ► Strongly NP-complete problems‎ (1 C, 4 P)
• ► Sudoku‎ (23 P, 2 F)

T

• ► Tetris‎ (1 C, 30 P)

W

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

• NP-complete

*

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

3

• 3-dimensional matching

B

• Battleship (puzzle)
• Berth allocation problem
• Bipartite dimension
• Boolean satisfiability problem

C

• Circuit satisfiability problem
• Clique cover problem
• Clique problem
• Closest string
• Crossword

D

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

E

• Edge dominating set
• Exact cover

F

• Feedback arc set
• Feedback vertex set
• Fifteen puzzle

G

• Generalized assignment problem
• Graph coloring
• Graph partition

H

• Hamiltonian completion

H cont.

• Hamiltonian path
• Hamiltonian path problem
• Hatena Satena
• Hitting set

I

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

J

• Job-shop problem

K

• Kakuro
• Knapsack problem

L

• Light Up
• Longest common subsequence problem
• Longest path problem

M

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

N

• Nonogram

N cont.

• Nurikabe

O

• One-in-three 3SAT

P

• Partition problem

Q

• Quadratic residue
• Quadrel

R

• Route inspection problem

S

• SameGame
• (SAT, ε-UNSAT)
• Satisfiability Modulo Theories
• Set cover problem
• Set packing
• Set splitting problem
• Set TSP problem
• Shortest total path length spanning tree
• Slitherlink
• Steiner tree problem
• Subgraph isomorphism problem
• Sudoku

T

• Tetris
• Traveling purchaser problem
• Travelling salesman problem

U

• Unit disk graph

V

• Vehicle routing problem
• Vertex cover
• Vertex cycle cover