Computational Complexity Classes & Reductions

← Back to Domain-Specific Families

Abstractions about classifying computational problems by resource bounds, reductions, approximation, hierarchy, sparsity, and descriptive complexity. They include circuit classes, counting and polynomial hierarchies, identity testing, switching arguments, Kolmogorov complexity, and open structural conjectures.

22 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.
• Berman–Hartmanis conjecture — The conjecture that every pair of NP-complete languages is related by a polynomial-time computable bijection whose inverse is also polynomial-time computable.
• Boolean hierarchy — The hierarchy of complexity classes obtained from finite Boolean combinations of NP languages.
• Computational complexity theory — The theory classifying computational problems by resource requirements and reductions under explicit models of computation.
• 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.
• Existential theory of the reals — The set and associated decision problem of true existential sentences formed from polynomial equalities and inequalities over real variables.
• 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.
• 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.
• 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.
• Polynomial identity testing — The computational problem of deciding whether an algebraic expression or arithmetic circuit represents the identically zero polynomial rather than merely vanishing at selected inputs.
• 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.
• 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.