Savitch's Theorem (Complexity Theory), Statement and Proof

[RIP to Walter Savitch, who passed away earlier this year.]

Timeline:
0:00 - Intro
0:58 - Brute-force simulation
4:00 - Analysis of brute-force space
5:40 - Idea to re-use space
8:40 - The CANYIELD function
13:30 - Recursive cases
21:20 - Analysis of total space needed

Youtube Live Streaming (Sundays) - subscribe for when these occur.

Merch:

▶SEND ME THEORY QUESTIONS◀

▶ABOUT ME◀
I am a professor of Computer Science, and am passionate about CS theory. I have taught many courses at several different universities, including several sections of undergraduate and graduate theory-level classes.

[EasyTheory]

Thanks to Micah Wood (Platinum), and Josh Hibschman, Timmy Gy, Patrik Keinonen, and Travis Schnider (Silver) for helping support this video. If you want to contribute, links are in the video description.

[judgebot]

just brilliant mate. Kind of content youtube was made for . Enjoyed every bit of this video

[eugut]

In 4:40 Shouldn't be space=d^(2^(f(n))?

[brendawilliams]

Thankyou. Are you using a reverse at some Turin machine state

[sambhunathdey]

Fine demonstrations.
Is it true for n dim space ?

[pinacolada]

is f(n) in this case log n? because the space can be seen as SPACE(f(n)^2) and the reachability should bein SPACE(log^2 n)...?

[AliAhmadi-uv]

Can anyone please explain why depth is 2^ O(f(n))?

[DannyPhantumm]

You would have got my subscription, but too many ads man. Isn't the typical YT approach to build a sizeable subscriber count before monetizing?