Uploaded April 2018 | Updated September 2026, 11 hours 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: review of space/time complexity classes and relationships, P=NP -type open problems, gap and speedup theorems, axiomatic complexity theory, alternation, alternating complexity classes, alternation-related relationships, quantified Boolean formulas (QBF), Quantified Satisfiability (QSAT), two-player games, "completeness" of generalized games, the polynomial hierarchy, more open complexity class containment and non-containment problems, Chomsky hierarchy reloaded
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: review of space/time complexity classes and relationships, P=NP -type open problems, gap and speedup theorems, axiomatic complexity theory, alternation, alternating complexity classes, alternation-related relationships, quantified Boolean formulas (QBF), Quantified Satisfiability (QSAT), two-player games, "completeness" of generalized games, the polynomial hierarchy, more open complexity class containment and non-containment problems, Chomsky hierarchy reloaded
