Logarithmic and polynomial space classes
DSPACE(s(n)) and NSPACE(s(n)) contain decision languages solvable with O(s(n)) workspace by deterministic and nondeterministic Turing machines.
Key knowledge
DSPACE(s(n)) and NSPACE(s(n)) contain decision languages solvable with O(s(n)) workspace by deterministic and nondeterministic Turing machines. L=DSPACE(log n), NL=NSPACE(log n), PSPACE=⋃ₖ≥₁DSPACE(nᵏ), and NPSPACE=⋃ₖ≥₁NSPACE(nᵏ).
Conditions and scope
- For sublinear bounds use a separate read-only input tape, excluded from workspace, and a fixed finite tape alphabet; n is encoded input length.
- Deciders halt on every input and, for nondeterministic machines, every branch; acceptance means some accepting branch. Workspace can be reused, so a small space bound does not itself give a comparable time bound.
Sources · 2
References
Sources retain their recorded scope. A source link alone does not establish verification of every statement.
Massachusetts Institute of Technology2 sources
Evidence and review
Lecture 20 slide 2 read-only-input/work-tape definitions; Lecture 17 slide 2 deterministic/nondeterministic halting-space and PSPACE definitions. Polynomial-space definitions agree despite whether input cells are counted.
2026-10-10 · Independent AI editorial review: All241 compact claims, hypotheses, displayed equations/conventions and all596 origin semantic links read; entire241-entry author exact-source inspection matrix and declared limitations reviewed. Prior105 actual inherited Mathematics/Information records read for whole-inventory breadth. Targeted independent primary sections are listed below; this does NOT claim every cited source body or every proof was independently re-read. This is AI reference-content review, not human disciplinary certification, exhaustive textbook reproduction or experimental replication. Receipt: mathematics-information-independent-content-review.1.
Entry details
Permanent link to this entry ↗- Record identity
- info-space-complexity-classes
- Revision
- university-core.1
- Structured reference record
- University core expansion