Embedded Files
Poly-time reductions
Satisfiability problem
P, NP, NP-complete, NP-hard, co-NP, EXP
Independent set, vertex cover, set cover
Independent set, vertex cover, set cover
SAT, 3-SAT, Hamilton cycle, 3D-matching, graph coloring
Reduction of SAT to 3-SAT, and of 3-SAT to other problems. Showing NP-completeness.
Coping with NP-completeness:
Special cases, approximation algorithms, exponential algorithms
Page updated
Google Sites
Report abuse