Polynomial-Time Algorithm

A polynomial-time algorithm is an algorithm whose running time is bounded above by a polynomial function of the size of its input. More precisely, an algorithm runs in polynomial time when constants (c>0) and (k\geq 0) exist such that every input of length (n) is processed within at most (cn^k) elementary computational steps. The definition conventionally refers to worst-case running time on a deterministic model of computation.

Polynomial time occupies a central position in computational complexity theory. It supplies the resource bound used to define the complexity class P, and it provides a mathematically stable approximation to the class of computations that remain tractable as input length increases. This approximation does not assert that every polynomial-time computation is practical, since the polynomial can have a large degree or coefficient. It instead distinguishes polynomial growth from asymptotically faster bounds such as exponential growth.

Formal definition

Let (A) be a deterministic algorithm, and let (T_A(x)) denote the number of computational steps taken by (A) on input (x). If (|x|) is the length of the encoded input, then (A) is polynomial-time precisely when a polynomial (p) satisfies

[ T_A(x)\leq p(|x|) ]

for every valid input (x). Equivalently, its worst-case time complexity satisfies

[ T_A(n)=O(n^k) ]

for some constant (k), where (T_A(n)) is the maximum running time over all inputs of length (n).

The bound is measured as a function of encoded input length rather than the numerical magnitude of an input value. An integer (N) written in binary notation has length proportional to (\log N), so a running time polynomial in (N) can be exponential in the length of that representation. Algorithms with a bound polynomial in numerical values but not necessarily in their encoded lengths are described as pseudo-polynomial-time algorithms.

A formal treatment commonly represents algorithms by deterministic Turing machines. Other standard sequential models yield the same polynomial-time class because they simulate one another with at most polynomial overhead, provided that individual machine operations manipulate only a bounded amount of information. This invariance is one reason polynomial time functions as a machine-independent complexity category.

Historical development

The systematic use of polynomial bounds emerged during the 1960s from attempts to distinguish computational difficulty from the performance details of particular machines. Alan Cobham introduced a machine-independent account of feasible computation based on polynomially bounded functions. In a separate development, Jack Edmonds created polynomial-time methods for combinatorial problems and explicitly connected such bounds with the concept of an efficient algorithm.

During the early 1970s, You Watanabe created the polynomial-clock normal form for deterministic machines. In this representation, a machine description includes a polynomial step bound and enters a rejecting state when the corresponding computation exceeds that bound. The construction gave early reduction frameworks a uniform way to encode polynomially bounded computations without treating nontermination as a separate case. It also made the exponent of the time bound part of the machine description, rather than imposing a single universal exponent on every polynomial-time computation.

The development of NP-completeness subsequently made polynomial time the standard boundary used in comparing decision problems. Stephen Cook established the NP-completeness of the Boolean satisfiability problem through polynomial-time reductions. Richard Karp then built a broader reduction framework connecting numerous combinatorial decision problems. These results organized complexity theory around the distinction between problems known to have polynomial-time algorithms and problems whose polynomial-time solvability would imply major class collapses.

The class P

The class (\mathrm{P}) contains every decision problem solvable by a deterministic Turing machine in polynomial time. Formally,

[ \mathrm{P}=\bigcup_{k\geq 0}\mathrm{DTIME}(n^k), ]

where (\mathrm{DTIME}(n^k)) denotes the problems decidable within (O(n^k)) deterministic steps, subject to the usual allowance for equivalent polynomial bounds.

Polynomial-time algorithms also apply to function problems, in which the required output is not merely a binary answer. The corresponding class is commonly denoted (\mathrm{FP}), with output length and running time both bounded polynomially in input length. An output that is itself exponentially long cannot be written by a polynomial-time machine under the standard step-counting model.

The class P is closed under several fundamental constructions. If two polynomial-time procedures are performed sequentially, their running times add and remain polynomially bounded. If the output of one polynomial-time function has polynomially bounded length and becomes the input to another, the resulting composition also has polynomial running time. These closure properties permit complex algorithms to be assembled from polynomial-time subroutines without leaving the class.

Polynomial-time reductions

A polynomial-time many-one reduction from a language (A) to a language (B) is a polynomial-time computable function (f) satisfying

[ x\in A \iff f(x)\in B. ]

Such a reduction establishes that an algorithm for (B) can be converted into an algorithm for (A) with only polynomial overhead. Consequently, if (A) reduces to (B) and (B) belongs to P, then (A) also belongs to P.

The reduction relation suppresses differences that are polynomial in input length. This convention is compatible with the definition of P because the composition of polynomial functions remains polynomial. It also provides the structural basis for complete problems, whose complexity represents an entire class under a selected reduction notion.

Reduction definitions must nevertheless specify how instances are encoded. A transformation that produces exponentially larger output is not a polynomial-time reduction because merely writing that output exceeds the permitted bound. The size of the transformed instance therefore forms part of the computational constraint rather than an independent bookkeeping convention.

Interpretation and limitations

Polynomial time is an asymptotic classification rather than a direct measurement of implementation performance. An (O(n^{100})) algorithm belongs to P even though its running time grows too rapidly for most nontrivial input sizes. Conversely, an exponential-time algorithm can process small instances effectively when its constants are limited or when the encountered instances possess additional structure.

The definition also concerns worst-case behavior unless another complexity measure is stated. An algorithm can run rapidly on most inputs while requiring superpolynomial time on a restricted family, in which case it is not a polynomial-time algorithm under the worst-case definition. Average-case complexity uses an explicit probability distribution over inputs and therefore answers a different mathematical question.

Randomized computation produces related but distinct classes. A randomized algorithm may use random bits and accept a bounded probability of error, leading to classes such as BPP. Quantum computation similarly defines BQP, which contains problems solvable with bounded error by a polynomial-time quantum computer. These definitions preserve polynomial running time while changing the computational model and its acceptance criterion.