Uploaded April 2018 | Updated September 2026, 22 minutes ago
This lecture is part of a course on the Theory of Computation, by Professor Gabriel Robins at the University of Virginia (CS3102 Spring 2018), with PowerPoint slides at http://www.cs.virginia.edu/~robins/cs3102 and other related videos at http://www.cs.virginia.edu/~robins/videos.html
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
This lecture is part of a course on the Theory of Computation, by Professor Gabriel Robins at the University of Virginia (CS3102 Spring 2018), with PowerPoint slides at http://www.cs.virginia.edu/~robins/cs3102 and other related videos at http://www.cs.virginia.edu/~robins/videos.html
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
