Lukas' Notes

Search titles, aliases and note text. Use # for tags.

NP-complete Decision Problem

1 min read

Definition

NP-complete Decision Problem

A -complete decision problem where NP.

Backlinks

192.026 Efficient Algorithms
3-SAT to 3-Horn SAT (Karp Reduction)
3-SAT to Subset Sum (Karp Reduction)
Chamberlin-Courant Winner Determination Decision Problem
Independent Set to Chamberlin-Courant Winner Determination (Karp Reduction)
Independent Set to Clique (Karp Reduction)
Independent Set to Proportional Winner Determination (Karp Reduction)
Independent Set to Vertex Cover (Karp Reduction)
Minimax Approval Voting Rule (COMSOC)
Proportional Winner Determination Decision Problem
SAT to Independent Set (Karp Reduction)
Vertex Cover to Dominating Set (Karp Reduction)

Created with Quartz v4.5.2 © 2026

GitHub