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

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