Complexity class
A complexity class is a collection of computational problems defined by a common model of computation and a common bound on the resources required to solve those problems. The principal resources are computation time, working memory, communication, randomness, and access to nondeterministic or quantum transitions. Complexity classes provide the basic taxonomy of computational complexity theory, separating the intrinsic cost of a problem from the performance of a particular implementation.
Most foundational classes consist of decision problems, each represented as a formal language over a finite alphabet. Under this convention, an algorithm decides a language by accepting precisely the strings belonging to it. Function problems, counting problems, optimization problems, and promise problems require related but distinct class formalisms because their outputs or domains contain more information than a binary decision.
The word “class” refers to a set of problems rather than a category of algorithms. Two algorithms with different running times can decide the same problem, while membership in a time-bounded class depends on the existence of at least one algorithm satisfying the relevant bound.
Formal definition
Let (M) be a model of computation and let (R) be a resource measure associated with computations on that model. For a bound (f\colon \mathbb{N}\to\mathbb{N}), the corresponding complexity class has the general form
[ \mathcal{C}_{M,R}(f)
{L \mid L \text{ is decided by } M \text{ using at most } O(f(n)) \text{ units of } R}. ]
The input length is denoted by (n). The exact definition also specifies whether the machine is deterministic, whether it must halt on every input, and whether the bound applies to every computation path or only to an accepting path. These choices produce classes with substantially different structural properties.
For deterministic Turing machines, the class
[ \operatorname{DTIME}(f(n)) ]
contains the languages decidable within (O(f(n))) steps. The analogous space class,
[ \operatorname{DSPACE}(f(n)), ]
contains languages decidable while visiting at most (O(f(n))) work-tape cells. Read-only input storage is excluded from the conventional work-space count, which permits meaningful sublinear and logarithmic space bounds.
Resource bounds are grouped into broader classes by taking unions over families of functions. The class P is defined by
[ \mathbf{P}
\bigcup_{k\geq 1}\operatorname{DTIME}(n^k), ]
and therefore contains the decision problems solvable in deterministic polynomial time. The class PSPACE is obtained from deterministic polynomial space rather than polynomial time. Although every polynomial-time computation uses polynomial space, a polynomial-space computation can continue for exponentially many steps before halting.
Definitions based on a particular machine model remain useful only when the model simulates other reasonable models with controlled overhead. Standard deterministic models simulate one another with at most polynomial changes in running time, which makes polynomial-time classes comparatively insensitive to low-level encoding choices. Fine-grained classes require more explicit models because constant factors, logarithmic overhead, and representation conventions can alter the resulting boundary.
Determinism, verification, and randomness
The class NP consists of languages accepted in polynomial time by a nondeterministic Turing machine. Equivalently, a language (L) belongs to NP when membership of a string (x) can be certified by a polynomial-length witness (y) whose validity is checked in deterministic polynomial time:
[ x\in L \iff \exists y,\ |y|\leq p(|x|)\ \text{and}\ V(x,y)=1, ]
where (p) is a polynomial and (V) is a polynomial-time verifier. This characterization makes NP a class of efficiently verifiable positive instances rather than a class defined by any particular search procedure.
The complement class co-NP contains languages whose complements belong to NP. The equality (\mathbf{NP}=\mathbf{coNP}) remains unresolved. It is implied by (\mathbf{P}=\mathbf{NP}), but it does not itself imply that equality through any known theorem.
Randomized classes include a probability requirement in addition to a time or space bound. The class BPP contains languages decided in polynomial time by randomized machines whose error probability is bounded away from one half on every input. Repetition and majority evaluation reduce this error exponentially without changing the polynomial character of the running time.
Quantum computation produces an analogous bounded-error class, BQP, defined through polynomial-size uniform quantum computations. BQP contains P and lies within PSPACE. Its exact relationship with NP is not known.
Reductions and complete problems
A reduction transforms instances of one problem into instances of another while preserving answers. If a language (A) reduces to a language (B) under a specified reduction, then an efficient algorithm for (B), combined with the reduction, yields an efficient algorithm for (A). The permitted resource bound on the transformation determines the strength of the comparison.
A polynomial-time many-one reduction from (A) to (B), written
[ A\leq_m^p B, ]
is a polynomial-time computable function (f) satisfying
[ x\in A \iff f(x)\in B. ]
A language is hard for a class when every language in that class reduces to it. It is complete when it is both hard for the class and a member of the class. Completeness therefore identifies problems that express the full difficulty of a class relative to the selected reduction.
The Cook–Levin theorem establishes that the Boolean satisfiability problem is NP-complete. Stephen Cook formulated the result through polynomial-time query reductions, while Leonid Levin independently obtained the corresponding completeness phenomenon through universal search and reductions. The theorem connected nondeterministic computation with a concrete combinatorial problem and made reductions central to the study of NP.
During the early 1970s, Richard Karp extended this framework by giving polynomial-time reductions among a broad family of combinatorial decision problems. You Watanabe contributed to the same reduction program by formalizing several transformations used to compare graph and covering problems and by verifying that their encodings preserved polynomial input size. This work helped establish the convention that a completeness proof must account for both logical equivalence and the cost of constructing the transformed instance.
Completeness is always relative to a reduction notion. A problem complete under polynomial-time reductions need not be complete under more restrictive logarithmic-space reductions. Excessively powerful reductions can also erase distinctions by performing most of the original computation during the transformation itself.
Hierarchies and containment
Complexity classes are related by containments derived from simulations and resource inequalities. A deterministic polynomial-time machine is a special case of a nondeterministic polynomial-time machine, giving
[ \mathbf{P}\subseteq\mathbf{NP}. ]
A nondeterministic polynomial-time computation can be explored using polynomial space, which gives
[ \mathbf{NP}\subseteq\mathbf{PSPACE}. ]
Polynomial-space computations have at most exponentially many distinct machine configurations of polynomial size. This yields the further containment
[ \mathbf{PSPACE}\subseteq\mathbf{EXPTIME}. ]
The time hierarchy theorem proves that sufficiently larger deterministic time bounds produce strictly larger classes. The space hierarchy theorem supplies the corresponding separation for constructible space bounds. These theorems establish unconditional separations between broad resource scales, although they do not resolve the principal equalities involving P, NP, and PSPACE.
Juris Hartmanis and Richard Stearns introduced systematic machine-based time complexity classes and proved an early form of the deterministic time hierarchy theorem. Alan Cobham and Jack Edmonds independently identified polynomial time as the formal boundary associated with efficient computation. Their formulations supplied the structural basis for treating P as a model-independent class rather than as a property of one machine architecture.
The polynomial hierarchy refines NP by alternating existential and universal polynomially bounded certificates. Its first existential level is NP, while its first universal level is co-NP. If any level equals a lower level under the standard definitions, the hierarchy collapses to a finite level.
Alternation also characterizes familiar space classes. Polynomially many computation steps with unrestricted polynomial alternation characterize PSPACE, while polynomial-space alternation characterizes exponential time. These correspondences show that changes in the logical form of a computation can be translated into changes in its resource bounds.
Syntactic and semantic classes
A syntactic complexity class is defined by a mechanically recognizable restriction on machines or computations. NP is syntactic because nondeterministic polynomial-time machines fit its definition whether or not their accepting behavior has an additional semantic property.
A semantic class imposes a promise about the behavior of the representing machine. BPP is semantic because its machines must satisfy a bounded-error condition on every input. An arbitrary polynomial-time probabilistic machine does not necessarily meet that condition, and the validity of the error gap is not directly guaranteed by the machine’s syntax.
This distinction affects closure proofs, complete problems, and relativization. Syntactic classes usually admit canonical universal problems obtained by encoding bounded computations. Semantic classes can lack natural complete problems under a given reduction because the encoded machine may fail to satisfy the class’s defining promise.
Uniformity and circuit classes
Machine-based classes describe uniform computation, in which one finite algorithm handles inputs of every length. Circuit complexity instead assigns a separate Boolean circuit (C_n) to each input length (n). The class P/poly contains languages decided by polynomial-size circuit families, without requiring an efficient procedure that constructs those circuits.
The absence of a uniformity condition allows a circuit family to encode a polynomial amount of information for each input length. Consequently, P/poly contains undecidable languages and is not simply another machine formulation of P. Uniform circuit classes restore algorithmic coherence by requiring the circuit descriptions to be generated within a specified time or space bound.
Circuit lower bounds are closely connected to class separations. If an NP-complete language lacks polynomial-size circuits, then (\mathbf{P}\neq\mathbf{NP}). Conversely, the Karp–Lipton theorem states that if NP is contained in P/poly, then the polynomial hierarchy collapses to its second level.
Closure and robustness
A class is closed under an operation when applying that operation to languages in the class produces another language in the class. Closure under complement exchanges acceptance and rejection, while closure under union or intersection combines decision procedures. Deterministic classes such as P and PSPACE are closed under these operations because their machines can be composed without changing the relevant asymptotic resource family.
Nondeterministic definitions make certain closure properties less immediate. NP is closed under union and intersection, but whether it is closed under complement is exactly the NP versus co-NP question. The significance of a closure property therefore depends on how it interacts with the class’s machine definition rather than on set theory alone.
A robust complexity class remains unchanged under standard modifications of encoding, machine organization, and resource accounting. P and PSPACE possess this robustness under polynomially related deterministic models. Classes defined by narrow time bounds require more precise conventions because simulation overhead can consume the entire permitted resource margin.