Uploaded April 2018 | Updated September 2026, 7 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 space/time complexity classes and their relationships, denseness of the space and time hierarchies, proper and non-proper containments among complexity classes, P=NP -type open problems, extended Chmosky hierarchy reloaded, other proper infinite hierarchies, Turing degrees and levels of impossibility, star-height regular hierarchy, infinities hierarchy, powersets, Rucker's book "Infinity and the Mind", fast-growing functions, gap theorem, non-computable time/space bounds, complexity gap between constant and log-log space, speedup theorem, Traveller's Dillema and Nash equilibria, complexity pathologies, abstract complexity theory, alternation, "Snakes on Every Plane", generalized two-player games, 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 (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 space/time complexity classes and their relationships, denseness of the space and time hierarchies, proper and non-proper containments among complexity classes, P=NP -type open problems, extended Chmosky hierarchy reloaded, other proper infinite hierarchies, Turing degrees and levels of impossibility, star-height regular hierarchy, infinities hierarchy, powersets, Rucker's book "Infinity and the Mind", fast-growing functions, gap theorem, non-computable time/space bounds, complexity gap between constant and log-log space, speedup theorem, Traveller's Dillema and Nash equilibria, complexity pathologies, abstract complexity theory, alternation, "Snakes on Every Plane", generalized two-player games, exploring the "Complexity Zoo"
