Undergrad Complexity at CMU - From P-Completeness to PSPACE-Completeness
Offered By: Ryan O'Donnell via YouTube
Course Description
Overview
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.
Syllabus
Introduction
PCompleteness
Reductions
Clauses
Logspace
Cooklevin Theorem
PSPACEComplete
Taught by
Ryan O'Donnell
Related Courses
理论计算机科学基础 | Introduction to Theoretical Computer SciencePeking University via edX 算法设计与分析(高级) | Advanced Design and Analysis of Algorithms
Peking University via edX The Introduction to Quantum Computing
Saint Petersburg State University via Coursera Computational Complexity Theory
Indian Institute of Technology Kanpur via Swayam Computational Complexity
IIT Hyderabad via Swayam