Deterministic space hierarchy
If S is space constructible, S(n)≥n, and s(n)=o(S(n)), then DSPACE(s(n))⊊DSPACE(S(n)).
Key knowledge
If S is space constructible, S(n)≥n, and s(n)=o(S(n)), then DSPACE(s(n))⊊DSPACE(S(n)). For example DSPACE(n)⊊DSPACE(n²): sufficiently larger constructible workspace permits new decision languages.
Conditions and scope
- This stated form uses the source's ≥n larger bound, with read-only input and workspace classes.
- The conclusion is existence of a separating language, not a claim that every algorithm benefits from added memory or that P≠PSPACE follows.
Sources · 2
References
Sources retain their recorded scope. A source link alone does not establish verification of every statement.
Evidence and review
Slides 6 page 4 space-hierarchy statement and pages 5–6 construction conventions; MIT Lecture 21 slides 8–9 give the diagonal space-bounded proof outline.
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-deterministic-space-hierarchy
- Revision
- university-core.1
- Structured reference record
- University core expansion