Uploaded March 2018 | Updated September 2026, 36 minutes 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: proof of Savitch's theorem, dramatic time-space tradeoffs, real-life time-money tradeoffs, P=NP and non-existence proofs, space closure under complementation / Immerman's theorem, enumeration of TM's for P / NP / PSPACE, denseness of infinite time and space hierarchies, pathological / non-computable time and space bounds, proper and non-proper complexity classes containment,additional P=NP -type open open questions, infinite dense proper hierarchies in the Chomsky hierarchy, star-depth regular hierarchy, Generalized Go is EXPTIME-complete, exploring the "Complexity Zoo"
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: proof of Savitch's theorem, dramatic time-space tradeoffs, real-life time-money tradeoffs, P=NP and non-existence proofs, space closure under complementation / Immerman's theorem, enumeration of TM's for P / NP / PSPACE, denseness of infinite time and space hierarchies, pathological / non-computable time and space bounds, proper and non-proper complexity classes containment,additional P=NP -type open open questions, infinite dense proper hierarchies in the Chomsky hierarchy, star-depth regular hierarchy, Generalized Go is EXPTIME-complete, exploring the "Complexity Zoo"
