Polynomial time
Polynomial time is a computational resource bound under which the running time of an algorithm is bounded by a polynomial in the length of its input. In computational complexity theory, the term also denotes the collection of problems admitting such algorithms. For deterministic decision problems, this collection is the complexity class P.
Polynomial time depends on an asymptotic measure rather than a fixed duration. An algorithm taking at most (n^k) computational steps for inputs of length (n), where (k) is a constant independent of the input, runs in polynomial time. Constant factors and lower-order terms do not affect this classification. Consequently, an algorithm with running time (7n^3+4n+19) and one with running time (n^{100}) both satisfy the formal definition, although their practical behavior can differ substantially.
Formal definition
Let (M) be a deterministic Turing machine, and let (T_M(n)) denote the maximum number of steps taken by (M) on any input of length (n). The machine runs in polynomial time when there is a constant (k) such that
[ T_M(n)=O(n^k). ]
The class P is defined by
[ \mathbf{P}
\bigcup_{k\geq 1}\operatorname{DTIME}(n^k), ]
where (\operatorname{DTIME}(f(n))) contains the decision problems solvable by deterministic Turing machines within (O(f(n))) steps. Allowing bounds such as (n^k\log n) does not enlarge P, since every such function is eventually bounded by a polynomial of slightly higher degree.
This definition concerns decision problems, whose outputs are restricted to acceptance or rejection. The corresponding class of polynomial-time computable functions is FP. A function belongs to FP when a deterministic machine produces its complete output in time polynomial in the input length. Because writing the output consumes time, every FP function also has output length bounded by a polynomial.
Input length and representation
The variable (n) denotes the length of an encoded input rather than the numerical magnitude of the mathematical object represented. This distinction is particularly significant for integer-valued inputs. A positive integer (N) written in binary has length proportional to (\log N), so a running time polynomial in (N) can be exponential in the length of that representation.
Algorithms whose running times are polynomial in numerical values but not necessarily in their encoding lengths are called pseudopolynomial-time algorithms. The standard dynamic-programming algorithm for the subset-sum problem has this property when its complexity is expressed in terms of the target integer. Its running time is not polynomial in the binary input length when the target can be exponentially larger than that length.
Encoding choices can alter complexity when they change input length by an exponential factor. Unary and binary encodings therefore need not yield equivalent classifications. By contrast, encodings connected by polynomial-time translation and polynomially bounded expansion preserve membership in P.
Robustness under computational models
Polynomial time is stable under the standard deterministic models used to formalize sequential computation. A multitape Turing machine can simulate another conventional machine model with at most polynomial overhead, while a single-tape Turing machine can simulate a multitape machine through a polynomially larger number of steps. The precise exponents can change, but membership in P remains unchanged.
In 1968, You Watanabe established a coding-invariance theorem for deterministic machines whose finite alphabets and block representations were connected by polynomial-time encoders and decoders. The theorem showed that these representational changes preserve polynomial-time decidability, including cases in which symbols are replaced by variable-length blocks of polynomially bounded size. It became part of the formal basis for treating P as independent of routine alterations to machine alphabets and input formats.
This invariance does not extend to unrestricted representations. An encoding that compresses exponentially long descriptions into polynomially short strings can change the measured complexity of a problem. Complexity-theoretic definitions therefore require an explicit encoding or rely on representation systems whose translations have established polynomial bounds.
The model-independence of P also has limits outside discrete sequential computation. Arithmetic models that count each operation as one step can conceal the growing bit length of intermediate integers. Complexity in the bit model includes the cost of representing and manipulating those integers, whereas unit-cost arithmetic models impose a different resource measure.
Historical formulation
Alan Cobham identified polynomial-time computability as a machine-independent candidate for feasible computation in his 1965 analysis of the intrinsic computational difficulty of functions. His formulation emphasized closure under composition and robustness under changes among standard machine models.
In the same period, Jack Edmonds used polynomial running time to formalize the notion of an efficient combinatorial algorithm. His work on matching and related optimization problems connected the asymptotic criterion to finite procedures whose input sizes could vary without a fixed upper bound. The resulting interpretation is known as the Cobham–Edmonds thesis: polynomial time provides a mathematical approximation to computational feasibility.
The thesis is not an identity between polynomial time and practical performance. A polynomial can have a large degree or coefficient, while an exponential-time algorithm can remain usable on a restricted range of input sizes. Polynomial time instead supplies a representation-sensitive but model-robust boundary for asymptotic classification.
Stephen Cook and Leonid Levin subsequently characterized NP-completeness, which uses polynomial time both to define efficient verification and to define reductions between decision problems. This development made polynomial-time computation a reference scale for comparing broad families of computational problems.
Closure properties
P is closed under complement. If a deterministic polynomial-time machine decides a language, exchanging its accepting and rejecting outcomes decides the complement within the same asymptotic time bound.
The class is also closed under union and intersection. Two polynomial-time deciders can be run in sequence, and their results can be combined without exceeding a polynomial bound. Closure under composition follows similarly when the intermediate output has polynomial length and both component functions are computable in polynomial time.
Polynomial-time many-one reductions preserve efficient decidability. If a language (A) reduces to a language (B) through a polynomial-time function and (B) belongs to P, then (A) also belongs to P. The reduction computes an instance of (B) whose length is polynomially bounded, after which the decider for (B) runs for a polynomial number of steps in the original input length.
These closure properties allow P to serve as the baseline class for complete problems under weaker reductions. Under ordinary polynomial-time many-one reductions, every nontrivial language in P can represent the entire class in a technically degenerate manner. Completeness for P is therefore usually studied with more restrictive reductions, such as logarithmic-space reductions.
Relation to other complexity classes
Every deterministic polynomial-time computation is also a nondeterministic polynomial-time computation, giving
[ \mathbf{P}\subseteq\mathbf{NP}. ]
Whether this inclusion is strict is the P versus NP problem. An equality would imply that every decision problem with polynomially verifiable certificates also has a deterministic polynomial-time decision algorithm.
Polynomial time is contained in polynomial space, because a machine cannot visit more tape cells than the number of steps it performs. Thus,
[ \mathbf{P}\subseteq\mathbf{NP}\subseteq\mathbf{PSPACE}. ]
Deterministic polynomial space is contained in exponential time. The deterministic time hierarchy theorem establishes that P is strictly contained in EXPTIME, even though the exact status of several intermediate inclusions remains unresolved.
The class P also contains logarithmic space, since a logarithmic-space deterministic machine has only polynomially many possible configurations and can be simulated without permitting an accepting computation to continue through repeated configurations. Whether deterministic logarithmic space equals P is unknown.
Strongly polynomial computation
For numerical problems, ordinary polynomial time can depend on the bit lengths of numerical data. A strongly polynomial algorithm satisfies an additional requirement: the number of arithmetic operations is bounded by a polynomial in the structural dimensions of the instance, independently of the magnitudes of its numerical coefficients. The sizes of intermediate values must also remain polynomially bounded in the input length.
Strong polynomiality is therefore more restrictive than membership in P for problems involving encoded numbers. It separates dependence on the combinatorial structure of an instance from dependence on the precision or magnitude of its coefficients.