Module
NP-Completeness and Intractability
Sign in to add this module to your path and practice.
About
Decision vs. optimization, P and NP, polynomial-time reductions, certificates/verifiers, NP-hardness/completeness, and classic problems (SAT, Independent Set, Vertex Cover, Clique, Hamiltonian Cycle, TSP decision version, etc.). Brief notes on coping strategies (approximation, exact exponential, special cases).
Goal
Prove a new problem is NP-complete via a clear polynomial reduction from a known NP-complete problem; explain the definitions of P, NP, and NP-complete; and recognize when a problem is unlikely to have a poly-time algorithm.
Unlocks
Tutor
Ask questions about this module.
Hi — I'm your tutor for NP-Completeness and Intractability. Ask about the concepts, goal, or where you're stuck.