Materials

We are using the L20 reduction slides slides.

Annotated slides from Mon Apr 11

Topics

• The idea of a reduction from one problem to another
• Examples that we have studied so far
• Independent set and Vertex cover as examples
• Theory of NP completeness
  • What does it mean for a language to be in NP?
  • What does it mean for a problem to be NP-complete?
  • What are examples of NP-complete problems