F2021 CS 340 Lecture 37 (Poly-Time Reduction, P, NP, P vs. NP, NP-complete, NP-hard)

This is the final lecture, we talked what builds to P vs. NP and how we can prove a problem is NP-complete. We also talked about where you may encounter NP-complete problems, as examples, and how you can prove P=NP and CHANGE THE WORLD. Thank you everybody, have a beautiful day!

Time Stamps:
0:00 Remarks, timeline of remainder of course, read the Parallel Algorithms section.
2:00 Last Day's reduction
10:00 P and NP.
38:08 P vs. NP
40:46 NP-completeness, examples, some from other domains (and nuances [see the notes for more details if you like]), and one simple way to prove P=NP.
51:50 Thank you, closing.