NP-completeness
The Cook–Levin theorem and NP-completeness of specific decision problems, by the problem's domain; includes both machine-level Karp reductions and stated NP-completeness results.
- Cook–Levin theorem
- Satisfiability and constraint satisfaction
- Cliques, covers and domination in graphs
- Graph coloring, cuts and layouts
- Paths, cycles, trees and subgraph problems
- Number partitioning, knapsack and packing
- Set systems, assignment and location
- Scheduling problems
- Strings, puzzles and Latin squares
Loading dependency explorer…
The dependency explorer needs JavaScript and its graph data.