Lecture 17: Space Complexity, PSPACE, Savitch's Theorem

Name: Lecture 17: Space Complexity, PSPACE, Savitch's Theorem
Uploaded: 2021-10-06T12:45:17Z
Duration: 1 h 20 min 10 s
Description: Description: Quickly reviewed last lecture. Introduced space complexity. Defined SPACE\((f(n))\), NSPACE\((f(n))\), PSPACE, and NPSPACE. Proved \(TQBF\) ∈ PSPACE, \(LADDER_\bf{DFA}\) ∈ NSPACE(\(n\)), and \(LADDER_\bf{DFA}\) ∈ SPACE(\(n^2\)). Instructor: Prof. Michael Sipser

1:20:10

Description: Quickly reviewed last lecture. Introduced space complexity. Defined SPACE\((f(n))\), NSPACE\((f(n))\), PSPACE, and NPSPACE. Proved \(TQBF\) ∈ PSPACE, \(LADDER_\bf{DFA}\) ∈ NSPACE(\(n\)), and \(LADDER_\bf{DFA}\) ∈ SPACE(\(n^2\)).

Instructor: Prof. Michael Sipser