ConceptTheory & Algos
Space complexity
The class of problems that can be decided using a bounded amount of tape cells as a function of the input size.
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.
Opens up
Concepts that name this one as a prerequisite.
Lecturers
2Each in their own terms, from the easiest level.
Ryan O'Donnell
The amount of memory space an algorithm requires to run as a function of the input size.Michael Sipser
The number of tape cells a Turing machine visits during its computation.
Lectures that assume it
21The first 12 are shown.
- The Word RAM Model
- Procedures and Processes; Substitution Model (SICP Lecture 1b)
- Parallel Storage Allocation
- Games, Generalized Geography
- The Immerman-Szelepcsényi Theorem
- PSPACE-Completeness
- Time/Space Tradeoffs for SAT
- Divide & Conquer: Van Emde Boas Trees
- Persistent Data Structures
- Hierarchy Theorems (Time, Space, and Nondeterministic)
- Hopcroft–Paul–Valiant Theorem
- Hierarchy Theorems
Connections
34The lectures that define it or assume it, and the concepts next to it.
Concepts9
Show 3 moreShow fewer
Lectures25
- Space Complexity
- Course Introduction and Overview
- Savitch's Theorem and NL
- Space Complexity, PSPACE, Savitch's Theorem
- The Word RAM Model
- Procedures and Processes; Substitution Model (SICP Lecture 1b)
Show 19 moreShow fewer
- Parallel Storage Allocation
- Games, Generalized Geography
- The Immerman-Szelepcsényi Theorem
- PSPACE-Completeness
- Time/Space Tradeoffs for SAT
- Divide & Conquer: Van Emde Boas Trees
- Persistent Data Structures
- Hierarchy Theorems (Time, Space, and Nondeterministic)
- Hopcroft–Paul–Valiant Theorem
- Hierarchy Theorems
- NL-Completeness and Logspace Reductions
- From P-Completeness to PSPACE-Completeness
- IP = PSPACE
- Impagliazzo T Wigderson, and Nisan's Pseudorandom Generators
- Oracle Turing Machines and P^NP
- Computational Models: Turing Machines
- L and NL, NL = coNL
- Provably Intractable Problems, Oracles
- Quantum Complexity