Skip to content

Computational Complexity

← Back to Domain-Specific Abstractions by Domain

26 domain-specific abstractions whose origin domain is Computational Complexity.

  • 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.
  • Average-case complexity — The expected computational resource usage of an algorithm or problem under an explicitly specified probability distribution over inputs of each size.
  • 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.
  • 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.
  • Interactive proof system — A protocol in which a computationally unbounded but untrusted prover exchanges messages with a resource-bounded randomized verifier to establish language membership with completeness and soundness guarantees.
  • 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.
  • MAX-3SAT — The optimization problem of assigning truth values to maximize the number or weight of satisfied clauses in a Boolean formula with at most three literals per clause.
  • 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.
  • 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)).
  • 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.
  • Sparse language — A formal language containing at most polynomially many strings of each input length, regardless of how difficult membership may be to decide.