ConceptTheory & Algos
PSPACE
The class of decision problems solvable by a Turing machine using a polynomial amount of space.
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 complexity5Complexity classes3Polynomial space2Polynomial time2Turing machine2Deterministic Turing machine1Polynomials1SPACE(f(n))1
Opens up
Concepts that name this one as a prerequisite.
Lecturers
3Each in their own terms, from the easiest level.
Ryan O'Donnell
Michael Sipser
The class of languages decidable by a deterministic Turing machine using a polynomial amount of space.Scott Aaronson
The class of problems that can be computed with a polynomial amount of memory and up to exponential time.
Lectures that assume it
7Connections
22The lectures that define it or assume it, and the concepts next to it.