Lukas' Notes

NP-hard Decision Problem

1 min read

Definition

NP-hard Decision Problem

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

Backlinks

192.026 Efficient Algorithms
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