# Intractability

algonotes

lecturenotes

We recap the complexity classes P, NP, NP-complete, NP-hard. We also show the following reductions:

- From 3SAT to Independent Set
- From 3SAT to 3-Coloring
- From 3SAT to 3-Dimensional Matching
- From 3-Dimensional Matching to Subset Sum