Skip to content

Space Complexity & Hierarchies

← Back to Domain-Specific Families

Abstractions about computational space classes, hierarchy and speedup theorems, padding, description length, and resource-bounded complexity.

11 abstractions in this family — domain-specific abstractions that sit near one another in structural-signature space (k-means over structural-signature embeddings). Each is shown with its short description.

  • Description number — A natural-number encoding of a Turing machine's finite transition description under a fixed universal-machine alphabet and coding scheme.
  • DSPACE — The deterministic space-complexity resource and associated classes of decision problems solvable by a deterministic Turing machine using a bounded amount of work-tape memory.
  • ESPACE — Classify decision problems solvable by a deterministic Turing machine using at most single-exponential workspace, conventionally \(\bigcup_{c>0}\mathrm{DSPACE}(2^{cn})\).
  • EXPSPACE — Classify decision problems solvable by a deterministic Turing machine using at most exponential workspace in the input length, allowing arbitrary finite exponential exponents through a union of space bounds.
  • Linear speedup theorem — The Turing-machine result that any fixed constant-factor reduction in running time can be obtained by enlarging the tape alphabet, up to lower-order overhead.
  • NSPACE — A family of complexity classes containing decision problems solvable by nondeterministic Turing machines using at most a specified asymptotic amount of work space.
  • Padding argument — A complexity-theoretic proof technique that appends irrelevant symbols to change input length and thereby translate one resource bound into another while preserving membership in the encoded language.
  • PolyL — The deterministic complexity class of decision problems solvable with polylogarithmic work space, DSPACE((log n)^O(1)).
  • PSPACE — The complexity class of decision problems solvable by a deterministic Turing machine using polynomial workspace.
  • SL (complexity) — The complexity class Symmetric Logspace, equivalently problems log-space reducible to undirected s–t connectivity and, by Reingold's theorem, equal to deterministic logspace L.
  • Space Hierarchy Theorem — A complexity separation theorem showing that sufficiently larger constructible workspace bounds decide strictly more languages, in deterministic and nondeterministic forms.