Algorithms for NP-Hard Problems (Section 22.1: Reductions Revisited)

Previous videos offered an algorithmic toolbox for tackling NP-hard problems, be it by fast heuristic algorithms or better-than-exhaustive- search exact algorithms. How do you know when you must resort to this toolbox? If your boss gives you a problem and tells you it’s NP-hard, fine. But recognizing NP-hard problems encountered in the wild—level-3 requires a trained eye. This and the next six videos begins with a single NP-hard problem (3-SAT) and concludes, after 18 reductions, with a list of 19, including all the problems studied earlier in this playlist. You can use this list as a starting point for NP-hardness proofs, and these reductions as templates for your own. Accompanies the book Algorithms Illuminated, Part 4: Algorithms for NP-Hard Problems (http://www.algorithmsilluminated.org/) Full playlist: https://www.youtube.com/playlist?list=PLEGCF-WLh2RK6lq3iSsiU84rWVee3A-hz