Skip to content

Computational Complexity Classes & Hierarchies

← Back to Domain-Specific Families

Abstractions about the theory of computational complexity, defining resource-bounded classes such as AC0, PSPACE and EXPSPACE, hierarchies built from bounded computation like the polynomial hierarchy and counting hierarchy, and proof techniques used to separate or reduce them, including padding arguments and the switching lemma.

30 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.

  • AC (complexity) — A circuit-complexity hierarchy of languages decidable by polynomial-size, polylogarithmic-depth Boolean circuits with unbounded-fan-in AND and OR gates.
  • AC0 — The circuit-complexity class of Boolean functions computed by polynomial-size, constant-depth families with unbounded-fanin AND and OR gates and input-level negations.
  • Arithmetic circuit complexity — The resource complexity of computing a polynomial with a directed acyclic circuit of field constants, variables and arithmetic gates.
  • AWPP — A counting-complexity class whose language decisions are represented by GapP functions that approximate a normalized acceptance indicator within bounded error.
  • Boolean hierarchy — The hierarchy of complexity classes obtained from finite Boolean combinations of NP languages.
  • Computational problem — A formally specified relation between encoded instances and acceptable solutions sought by an algorithm.
  • Constructible function — A resource-bound function whose value can be produced within the time or space bound it specifies, making the bound usable in complexity hierarchy arguments.
  • Counting hierarchy — The oracle hierarchy beginning with P and iterating PP computation, analogous to the polynomial hierarchy with majority counting in place of existential nondeterminism.
  • 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})\).
  • Existential theory of the reals — The set and associated decision problem of true existential sentences formed from polynomial equalities and inequalities over real variables.
  • 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.
  • FNP (complexity) — The class of polynomially balanced search relations whose proposed solutions can be verified in deterministic polynomial time.
  • Fully polynomial-time approximation scheme — An approximation scheme whose running time is polynomial both in input size and in the reciprocal of the requested error tolerance.
  • Kolmogorov complexity — The length of the shortest program for a fixed universal description language that outputs a given finite object and halts.
  • 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.
  • Parity P — The complexity class of decision problems for which a nondeterministic polynomial-time machine accepts exactly when it has an odd number of accepting computation paths.
  • Parsimonious reduction — A problem transformation that preserves the exact number of solutions.
  • PolyL — The deterministic complexity class of decision problems solvable with polylogarithmic work space, DSPACE((log n)^O(1)).
  • Polynomial hierarchy — A nested hierarchy of decision-problem classes formed by bounded alternations of existential and universal polynomial-time computation, generalizing NP and coNP within PSPACE.
  • PSPACE — The complexity class of decision problems solvable by a deterministic Turing machine using polynomial workspace.
  • Reduction (complexity) — An algorithmic transformation from instances of one computational problem to another that preserves answers and is efficient enough to transfer solvability or hardness results.
  • SC (complexity) — The complexity class of decision problems solvable by one deterministic algorithm using polynomial time and polylogarithmic space.
  • Set splitting problem — The decision problem of two-coloring a finite set so every member of a specified family contains both colors.
  • 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.
  • Sophistication (complexity theory) — An algorithmic-information measure of the shortest model in which a string is a typical member at a declared significance tolerance.
  • Sparse language — A formal language containing at most polynomially many strings of each input length, regardless of how difficult membership may be to decide.
  • Switching lemma — A random-restriction theorem showing that a bounded-width CNF or DNF Boolean formula usually simplifies to a shallow decision tree and can therefore switch to the opposite normal form.