Explore Savitch's Theorem and NL in this undergraduate Computational Complexity Theory lecture from Carnegie Mellon University's Course 15-455. Delve into topics such as pseudocode, space complexity, recursion, and NL codecorrectness. Learn from Professor Ryan O'Donnell as he covers the remaining portions of Sipser Ch. 8.1 and 8.4. Gain valuable insights into this fundamental theorem and its implications for nondeterministic logarithmic space complexity.
Undergrad Complexity at CMU - Savitch's Theorem and NL
Overview
Syllabus
Introduction
Savitchs Theorem
Pseudocode
Space Complexity
Recursion
NL
Code
correctness
Taught by
Ryan O'Donnell
