Overview
Save Big on Coursera Plus. 7,000+ courses at $160 off. Limited Time Only!
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.
Syllabus
Introduction
Savitchs Theorem
Pseudocode
Space Complexity
Recursion
NL
Code
correctness
Taught by
Ryan O'Donnell