Uploaded April 2018 | Updated September 2026, 15 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:resource-bounded computation, the "Complexity Zoo", the extended Chomsky hierarchy reloaded, NP-completeness, tractability,
computation vs. decision, non-determinism, reducibilities reloaded, polynomial-time reductions, problem transformations, NP-hardness and NP-completeness, P=co-P, is NP=co-NP?, logspace reductions, Boolean Satisfiability (SAT), history of the Cook-Levine theorem, Garey & Johnson's classic NP-completeness book, practical benefits of NP-completeness, proof of the Cook-Levine theorem
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:resource-bounded computation, the "Complexity Zoo", the extended Chomsky hierarchy reloaded, NP-completeness, tractability,
computation vs. decision, non-determinism, reducibilities reloaded, polynomial-time reductions, problem transformations, NP-hardness and NP-completeness, P=co-P, is NP=co-NP?, logspace reductions, Boolean Satisfiability (SAT), history of the Cook-Levine theorem, Garey & Johnson's classic NP-completeness book, practical benefits of NP-completeness, proof of the Cook-Levine theorem
