# Category:NP-complete problems

Computing portal |

Here is a list of articles in the category **NP-complete problems** of the Computing portal that unifies foundations of mathematics and computations using computers. ==See also==

## Pages in category "NP-complete problems"

The following 85 pages are in this category, out of 85 total.

- 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)*