Complexity Class

Sort computational problems into a small lattice of named strata — P, NP, PSPACE, and their kin — by the resource bound they admit under a fixed model, so that placing a problem by one reduction transitively imports its whole feasibility profile.

Version

v2 · 2026-09-19 · History

Domain-specific #

189

Domain group

Applied Sciences & Engineering

Origin domain

Computer Science & Software Engineering

Subdomain

Computational Complexity Theory → Computer Science & Software Engineering

Core Idea

A complexity class is a named set of computational problems whose members share the same resource bound under a fixed model of computation — canonically P, NP, PSPACE, EXPTIME, BPP, BQP. Four ingredients define a class: a model (deterministic, nondeterministic, quantum, circuit), a resource (time, space, randomness), a bound as a function of input size, and an acceptance criterion. Reducibility establishes a partial order — if A reduces to B, B is at least as hard as A — and completeness identifies the hardest members, into which every class member reduces.

How would you explain it like I'm…

Puzzle Bins by Effort

Imagine sorting puzzles into bins by how much work they take to solve with a certain kind of helper. Puzzles that a quick helper can finish go in one bin, and puzzles that need a huge amount of time go in another. Each bin is a complexity class.

Problem Groups by Computing Cost

A complexity class is a named group of problems that a computer can solve within the same kind of limit. The limit might be on time, like 'not too many steps as the problem gets bigger', or on memory. For example, P is the group of problems a normal computer can solve reasonably quickly, and NP is the group whose answers can be checked reasonably quickly. Scientists also compare problems by turning one into another: if problem A can be turned into problem B, then B is at least as hard as A. One of the biggest unsolved questions is whether P and NP are really the same group.

Resource-Bounded Problem Class

A complexity class is a set of problems that can be solved within a certain limit on a resource, like time or memory, using a particular kind of computer model. Four things define a class: the model (deterministic, nondeterministic, randomized, quantum, circuits), the resource measured (time, space, randomness), the bound as a function of input size (polynomial, logarithmic, exponential), and how the machine accepts an answer. Well-known classes include P (polynomial time), NP (answers checkable in polynomial time), PSPACE (polynomial memory), EXPTIME (exponential time), BPP (randomized, with bounded error) and BQP (quantum, with bounded error). Reductions compare problems: if A reduces to B, a fast solution to B gives a fast solution to A. NP-complete problems are in NP and every NP problem reduces to them. It is proved that P ⊆ NP ⊆ PSPACE ⊆ EXPTIME and that P ≠ EXPTIME, but P versus NP is still open.

 

A complexity class is a named set of computational problems sharing a resource bound under a fixed model of computation. Four ingredients define it: the model (deterministic, nondeterministic, probabilistic, quantum, circuit-based), the resource (time, space, randomness, communication), the bound as a function of input size (logarithmic, polynomial, exponential), and the acceptance criterion. A problem belongs to a class if some algorithm in that model solves it within the bound. Canonical examples are P, NP (polynomial-time verifiable, equivalently nondeterministic polynomial time), PSPACE, EXPTIME, BPP, and BQP. Reductions, with polynomial-time many-one reductions as the standard case, order problems by hardness, and completeness picks out the hardest members, as with NP-complete problems. The theory's architecture is the web of containments and separations: P ⊆ NP ⊆ PSPACE ⊆ EXPTIME is proved, P ≠ EXPTIME follows from the time hierarchy theorem, and P vs NP, NP vs co-NP, and NP vs PSPACE remain open. Placing a new problem in this map — for example, proving it NP-complete — immediately indicates that no polynomial-time exact algorithm is known or expected and points toward approximation, parameterized, or practical exponential-time approaches.

Scope of Application

A complexity class applies literally wherever its precondition holds: a precisely specified model of computation with a resource bounded as a function of input size — all within theoretical computer science.

• Algorithm design — the home: classifying a problem as P, NP-hard, or FPT before any search begins.
• Cryptography — one-way functions and public-key security stated relative to class assumptions.
• Approximation theory — APX, PTAS, FPTAS quantifying how well NP-hard problems can be approximated.
• Parameterized complexity — FPT, W[1], W[2] refining NP-hardness by an isolated parameter.
• Quantum-advantage theory — BQP and its relations to BPP, NP, PH.
• Game-theoretic complexity — PPAD for Nash equilibrium, PLS for local-search equilibria.

Clarity

Naming a problem's complexity class clarifies what one is asking for when one asks for "an algorithm": "polynomial time?" and "exponential time that runs acceptably?" are sharply different requests, so a designer can commit to a target before searching. Once a problem is pinned as NP-hard, the hunt for an exact polynomial-time algorithm is either futile or revolutionary. Its second act is to make a classification transitive news — one reduction imports everything already known about the class.

Manages Complexity

The universe of computational problems is unbounded and individually opaque. Complexity classes collapse it onto a small fixed lattice: every problem sorts by four parameters into about a dozen strata, and the practitioner reasons about the stratum. The lever that makes this usable is reduction: to place a fresh problem, exhibit a reduction to or from a canonical complete problem (3-SAT, VERTEX-COVER), and a single reduction settles the whole feasibility bundle transitively. The astronomical zoo reduces to a small map plus a navigation rule.

Abstract Reasoning

A complexity class licenses a classification move (placing a fresh problem by reducing it to a known anchor, with reduction direction load-bearing), a diagnostic move (reading algorithmic prospects off class membership in one stroke), a boundary-drawing move (fixing what is asked by resource and bound, and reasoning within proved containments while flagging open separations as conditional), an interventionist move (converting a hardness verdict into approximation, parameterized tractability, or fast-in-practice exponential algorithms), and a predictive move (one classification forecasts the whole research trajectory).

Knowledge Transfer

Within theoretical computer science the complexity class transfers as mechanism, intact, as the workhorse vocabulary of nearly every feasibility claim — the four parameters, reduction-based classification, completeness anchors, and containment lattice move without translation across algorithm design, cryptography, approximation theory, parameterized and quantum complexity, and game-theoretic complexity, anywhere a formal model of computation is in play. Beyond formal computation the apparatus does not travel: the model, the bounds as functions of input size, reducibility, and completeness all presuppose a specified machine. Calling a staffing problem "NP-hard" by feel is metaphor — there is no 3-SAT to reduce from. The thin portable residue is carried by Classification plus Complexity.

Relationships to Other Abstractions

Current abstraction Complexity Class Domain-specific

Parents (2) — outgoing typed relations

• Complexity Class is a kind of Classification Prime

  Complexity-class analysis is classification specialized to sorting formal problems by explicit machine, resource, bound, and acceptance rules.

• Complexity Class includes Complexity (Time/Space) Prime

  A time-or-space resource scaling rule is an internal defining constituent of a complexity class rather than merely a neighboring measurement.

Children (15) — abstractions linked here by typed relations

• Exact Quantum Polynomial Time Domain-specific is a kind of Complexity Class

  Exact Quantum Polynomial Time is a Complexity Class containing decision problems solved uniformly in quantum polynomial time with zero error.

• FPT (complexity class) Domain-specific is a kind of Complexity Class

  FPT is a complexity class defined by fixed-parameter tractable running-time bounds.

• LOGCFL Domain-specific is a kind of Complexity Class

  LOGCFL is a complexity class defined by log-space reducibility to context-free languages.

• NC (complexity) Domain-specific is a kind of Complexity Class

  NC (complexity) is a domain-specific kind of complexity class under the frozen identity and differentia. Complete-catalog comparison found the corresponding live broader identity.

• NE (complexity) Domain-specific is a kind of Complexity Class

  NE is a complexity class bounded by nondeterministic single-exponential time.

▸ Show 10 more

Hierarchy paths (6) — routes to 5 parentless roots

• Complexity Class → is a kind of Classification

Show alternative paths (5)

Neighborhood in Abstraction Space

Complexity Class sits in a moderately populated region (53^rd percentile for distinctiveness): it has near-neighbors but no dense thicket of look-alikes.

Family — Computational Complexity & Hardness (18 abstractions)

Nearest neighbors

• NTIME — 0.88
• Computational hardness assumption — 0.87
• NEXPTIME — 0.86
• P versus NP Problem — 0.85
• Parallel computation thesis — 0.85

Computed from structural-signature embeddings · 2026-10-25