Uploaded March 2018 | Updated September 2026, 12 hours 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:review of 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 vs non- re-usability of time, Genie-in-a-Bottle, eliminating non-determinism w.r.t. time and space, Chomsky hierarchy reloaded, time complexity hierarchy, space complexity hierarchy, preview of Savitch's 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:review of 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 vs non- re-usability of time, Genie-in-a-Bottle, eliminating non-determinism w.r.t. time and space, Chomsky hierarchy reloaded, time complexity hierarchy, space complexity hierarchy, preview of Savitch's theorem
