Sign inSign in

Savitch's theorem

A theorem stating that any problem solvable by a non-deterministic Turing machine in S(n)S(n) space is solvable by a deterministic Turing machine in S2(n)S^2(n) space.
as Michael Sipser defines itMITThe wording closest to all 6 definitions
Watch it explained

Know first

Named as a prerequisite by the lectures that define this. The number is how many say so. A grey one has no page yet.

Space complexity5Turing machine3Non-deterministic Turing machine2Configuration1Deterministic space classes1Deterministic space complexity1Non-determinism1Non-deterministic space complexity1

Opens up

Concepts that name this one as a prerequisite.

Lecturers

2

Each in their own terms, from the easiest level.

  • Ryan O'Donnell

    Carnegie Mellon University · Undergraduate

    A theorem stating that deterministic space complexity classes are closed under squaring, specifically that ST-PATH can be solved in log⁡2n\log^2 n space.
    • 20:50The Immerman-Szelepcsényi Theorem
    • 43:37Space Complexity
    • 7:45Savitch's Theorem and NL
    • 1:17:50From P-Completeness to PSPACE-Completeness
  • Michael Sipser

    MIT · Undergraduate

Lectures that assume it

2

Connections

15

The lectures that define it or assume it, and the concepts next to it.

2 lecturers. Definitions are written by AI from each lecture’s transcript. A time with a play mark starts the lecture at the moment the lecturer says it.