CSC 341 (Fall 2021)

Reading: Savitch's Theorem

Savitch’s theorem states a surprising result: nondeterminism doesn’t matter for poly-space algorithms! In this class, we’ll deep-dive into the proof, highlighting the power of divide-and-conquer.