Undergrad Complexity at CMU - From P-Completeness to PSPACE-Completeness

Explore the intricacies of NP-completeness, P-completeness, and PSPACE-completeness in this comprehensive lecture from Carnegie Mellon University's Undergraduate Computational Complexity Theory course. Delve into topics such as reductions, clauses, logspace, and the Cook-Levin Theorem as part of the Spring 2017 15-455 course taught by Professor Ryan O'Donnell. Gain a deeper understanding of computational complexity theory through this 80-minute video, which covers Sipser Chapter 8.3 up to the PSPACE-completeness of TQBF. Enhance your knowledge of theoretical computer science and prepare for advanced concepts in complexity theory.