Theory of Computation (CS6160) Lecture 09 (Part 1 of 2), Professor Gabriel Robins

Specific topics covered in this lecture: resource-bounded computation, time and space complexity classes, time-space usage and tradeoffs, P / NP / PSPACE / EXPTIME / EXPSPACE / LOGSPACE, space-time relationships, re-usability of space, non-re-usability of time, Genie-in-a-Bottle, eliminating non-determinism w.r.t. time and space, Savitch's theorem, Chomsky hierarchy reloaded, infinite time complexity hierarchy, infinite space complexity hierarchy, revisiting diagonalization / dovetailing /pigeon-hole principle, pathological / non-computable resource bounds / functions