Category:NP-complete problems

N

• [+] Nonograms (6 P)

S

• [+] SAT solvers (4 P)
• [+] SMT solvers (2 P)

S cont.

• [+] Strongly NP-complete problems (3 P)
• [+] Sudoku (21 P, 2 F)

T

• [+] Tetris (1 C, 25 P)

W

• [+] Weakly NP-complete problems (3 P)

• NP-complete

*

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

3

• 3-dimensional matching

B

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

C

• Clique cover
• 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 path problem
• Hamiltonian completion

H cont.

• Hamiltonian path
• Hatena Satena
• Hitting set

I

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

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 (computer game)
• Minimum k-cut
• Monochromatic triangle

N

• Nonogram
• Nurikabe

O

• One-in-three 3SAT

P

• Partition problem

P cont.

• Post correspondence problem

Q

• Quadratic assignment problem
• Quadratic residue

R

• Route inspection problem

S

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

T

• Tetris
• Travelling salesman problem

U

• Unit disk graph

V

• Vehicle routing problem
• Vertex cover
• Vertex cycle cover