Uploaded March 2018 | Updated September 2026, 58 minutes 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:the course TAs talk at length to the class about cheating/plagiarism -related issues - please don't cheat!, the Chomsky hierarchy revisited, infinite time and space hierarchies, proof of Savitch's theorem, dramatic time-space tradeoffs, NPSPACE = PSPACE, space analogue of P=NP question, non-deterministic space is closed under complementation, Immerman'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:the course TAs talk at length to the class about cheating/plagiarism -related issues - please don't cheat!, the Chomsky hierarchy revisited, infinite time and space hierarchies, proof of Savitch's theorem, dramatic time-space tradeoffs, NPSPACE = PSPACE, space analogue of P=NP question, non-deterministic space is closed under complementation, Immerman's theorem
