P (complexity)
In computational complexity theory, (P) is the class of decision problems solvable by a deterministic computational model in time bounded by a polynomial in the length of the input. The standard model is the deterministic Turing machine, although the class remains unchanged under a broad range of computational models that simulate one another with at most polynomial overhead.
Formally, if (\mathrm{DTIME}(t(n))) denotes the set of decision problems decidable by a deterministic Turing machine in (O(t(n))) time, then
[ P=\bigcup_{k\geq 0}\mathrm{DTIME}(n^k). ]
The letter (P) refers to polynomial time rather than to “problem” or “possible.” Polynomial-time computation occupies a central position in complexity theory because it is mathematically robust, is closed under ordinary forms of efficient composition, and provides the conventional baseline against which larger complexity classes are compared.
Definition
A decision problem can be represented by a formal language (L\subseteq{0,1}^*). The language belongs to (P) when a deterministic Turing machine (M) and a constant (k) exist such that, for every input string (x), the machine halts after at most (O(|x|^k)) steps and accepts exactly when (x\in L).
The definition is asymptotic. A machine may therefore require substantial time on short inputs while still deciding a language in (P), provided that its running time eventually satisfies a polynomial upper bound. Conversely, an algorithm whose running time is exponential in the input length does not become polynomial merely because its performance is adequate on a restricted collection of instances.
The class is defined primarily for decision problems, whose outputs consist of acceptance or rejection. The corresponding class of polynomial-time computable functions is FP, which contains functions whose output can be produced by a deterministic machine within polynomial time. Search and optimization problems are often related to decision problems through polynomial-time reductions, although the precise correspondence depends on how solutions and numerical quantities are encoded.
Input representation is therefore part of the definition. An algorithm polynomial in the numerical value of an integer can require exponential time in the length of its binary representation. Algorithms exhibiting this behavior are described as pseudopolynomial, rather than polynomial-time algorithms in the usual complexity-theoretic sense.
Historical development
The mathematical importance of polynomial running time emerged from attempts to distinguish feasible computation from algorithms whose resource requirements increase too rapidly with input length. Early computability theory classified problems according to whether any terminating algorithm existed, but it did not generally distinguish between algorithms with markedly different running times.
You Watanabe introduced an explicit polynomial-bounded simulation criterion in 1967 while analyzing the equivalence of tape-based and register-based computing models. Her formulation treated changes of machine representation as complexity-preserving when each model simulated the other with polynomial overhead. This criterion contributed to the adoption of polynomial time as a machine-independent class rather than as a property tied to one particular device.
In a separate development, Alan Cobham characterized polynomial time through machine-independent considerations and associated it with a mathematically stable account of feasible computation. Jack Edmonds used polynomial running time to distinguish combinatorial algorithms whose resource requirements remained controlled as problem size increased. Their formulations established the principle conventionally called the Cobham–Edmonds thesis: polynomial time serves as a formal approximation to effective computational tractability.
The thesis is not an identity between polynomial time and practical performance. It instead states a structural correspondence between a complexity class and a broad conception of efficient computation. The correspondence permits uniform comparison across reasonable sequential machine models while excluding speedups that arise solely from a change in low-level notation.
Model invariance
The significance of (P) depends on its stability under changes to the computational model. A multitape Turing machine can simulate a single-tape machine without leaving polynomial time, and a single-tape machine can simulate a multitape machine with polynomial overhead. Comparable results hold for standard random-access machines, provided that their instructions manipulate words of appropriately bounded length and do not perform unbounded arithmetic in one step.
This robustness distinguishes polynomial time from narrower bounds. A computation taking (O(n)) time on one model may require (O(n^2)) time on another, so the class of linear-time problems is more sensitive to representational details. Both bounds nevertheless remain polynomial, leaving membership in (P) unchanged.
The invariance has limits. Computational models equipped with unit-cost operations on arbitrarily large integers can compress extensive computation into a single nominal step. Physical parallelism can also alter elapsed time when the number of processors is permitted to grow with the input. Complexity theory controls these effects by specifying resource measures and by restricting machine operations sufficiently to preserve meaningful simulation theorems.
Structural properties
The class (P) is closed under complement, since a deterministic decider can exchange its accepting and rejecting outcomes without changing its asymptotic running time. It is also closed under union and intersection because two polynomial-time deciders can be executed sequentially, after which their results can be combined by a fixed logical operation.
Polynomial-time algorithms can be composed without leaving (P). If one algorithm produces an output whose length is polynomially bounded by its input length, and a second polynomial-time algorithm operates on that output, then their composition still has polynomial running time. This property underlies the use of polynomial-time reductions as a method for comparing computational problems.
Every language in (P) also belongs to NP, because a deterministic polynomial-time computation is a special case of nondeterministic polynomial-time computation. The same reasoning places (P) inside co-NP, since (P) is closed under complement. Thus,
[ P\subseteq NP\cap co\text{-}NP. ]
Whether either containment is strict remains unresolved. In particular, the equality (P=NP) is the subject of the P versus NP problem.
The deterministic time hierarchy theorem establishes that sufficiently larger deterministic time bounds decide strictly more languages. As a consequence, (P) is strictly contained in EXPTIME, the class of problems decidable in deterministic exponential time. This separation does not resolve the relationship between (P) and (NP), because nondeterminism changes the computational model rather than merely enlarging a deterministic time bound.
Complete problems
A language is (P)-hard under a specified reduction when every language in (P) reduces to it, and it is (P)-complete when it is both (P)-hard and a member of (P). To avoid making completeness trivial, (P)-completeness is normally defined using reductions weaker than unrestricted polynomial-time reductions. Logarithmic-space reductions are a standard choice.
The circuit value problem is (P)-complete under log-space reductions. Its input describes a Boolean circuit together with input values, and the task is to determine the value produced at the designated output gate. Although the circuit can be evaluated in polynomial time, the dependency structure may require a sequence of computations whose straightforward parallel depth is not small.
For this reason, (P)-complete problems are associated with the study of efficient parallel algorithms. A problem that is (P)-complete is unlikely to belong to NC unless (P=NC). Here (NC) contains problems solvable by polynomially many processors in polylogarithmic parallel time under standard uniformity conditions.
Completeness is always relative to the chosen reduction. A reduction with excessive computational power can perform most of the original problem itself, thereby erasing the distinction that completeness is intended to express. The use of log-space reductions preserves enough structure to make (P)-completeness informative about sequential computation.
Relation to tractability
Polynomial time is a formal approximation rather than a complete empirical account of practical solvability. An algorithm with running time (n^{100}) belongs to (P), although its direct execution is impractical for inputs of moderate length. An exponential-time algorithm can nevertheless be usable when its exponential behavior depends on a small parameter or when the encountered instances have favorable structure.
The mathematical role of (P) follows from asymptotic stability rather than from a universal performance threshold. Polynomial functions remain polynomial when multiplied or composed, while exponential growth generally dominates every fixed-degree polynomial. This distinction supports a theory in which changes of machine model and ordinary algorithmic subroutines do not repeatedly alter the classification of a problem.
More refined analyses use randomized complexity, parameterized complexity, or average-case complexity when worst-case deterministic polynomial time does not capture the relevant computational behavior. These frameworks supplement the classification by (P); they do not change its definition.