Lukas' Notes

NP-complete Decision Problem

1 min read

Definition

NP-complete Decision Problem

A $C$ -complete decision problem where $C =$ NP.

Backlinks

192.026 Efficient Algorithms
3-SAT to Subset Sum (Karp Reduction)
Independent Set to Clique (Karp Reduction)
Independent Set to Vertex Cover (Karp Reduction)
SAT to Independent Set (Karp Reduction)
Vertex Cover to Dominating Set (Karp Reduction)

Created with Quartz v4.5.2 © 2026

GitHub