Theory of Computation (CS3102), Lecture 24, Professor Gabriel Robins, Spring 2018

Specific topics covered in this lecture: classic NP complete problems, decision vs. optimization, building optimizers from deciders, "playing Twenty-Questions", graph clique problem is NP-complete, independent set problem is NP-complete, graph colorability is NP-complete, "OR gate" gadget, example of reducing Boolean satisfiability to graph 3-colorability, colorability of degree-bounded graphs, 1-colorability, 2-colorability, degree-0 / degree-1 / degree-2 colorability, NP-completeness of max-degree-4 graph colorability