Intractability

algonotes
lecturenotes
Published

August 1, 2023

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

  1. From 3SAT to Independent Set
  2. From 3SAT to 3-Coloring
  3. From 3SAT to 3-Dimensional Matching
  4. From 3-Dimensional Matching to Subset Sum

© 2022 • Neeldhara Misra • Credits •

 

Corrections? Please leave a comment here or a PR in this repository, thanks!

I’d rather be a failure at something I love than a success at something I hate.

George Burns

You live and you learn — at any rate, you live.

Douglas Adams

A problem worthy of attack proves its worth by fighting back.

Paul Erdos