Uploaded April 2018 | Updated September 2026, 11 hours ago

---

This lecture is part of a course on the Theory of Computation, by Professor Gabriel Robins at the University of Virginia (CS6160 Spring 2018), with PowerPoint slides at http://www.cs.virginia.edu/~robins/cs6160/ and other related videos at http://www.cs.virginia.edu/robins/videos.html

Specific topics covered in this lecture: review of some classic NP-complete problems, decision vs. optimization problems, building an optimizer from a decider, playing "Twenty Questions", "Obi-Wan has taught you well!", counting solutions and #P, NP and efficient verifiability, "guess and verify" algorithms, complexity of sorting vs verifying sortedness, graph clique problem is NP-complete, hard problems can have easy instances, independent set problem is NP-complete, graph coloraility is NP-complete, "gadget"-based reductions, solving satisfiability via colorability, colorability of degree-contrained graphs, odd cycles, colorability of max-degree-4 graphs is NP-complete, planar graph colorability, K_5 and K_3,3 are not planar, Kuratowski's theorem