NP-Completeness

NP-Completeness (see [DPV] Chapter 8): 

NP, Reductions – notes and NP1 lecture video
3-SAT – notes and NP2 lecture video
Graph problems  – notes and NP3 lecture video
Knapsack – notes and NP4 lecture video
Halting problem – notes and NP5 lecture video