PolynomialTime

Polynomial time, in computational complexity theory, refers to an upper bound on the running time of an algorithm that grows as a polynomial function of the size of its input. If an algorithm runs in time O(n^k) for some constant k and input length n, it is said to run in polynomial time. This definition uses the length of the input encoding; different encodings can change the measured input size.

The class P consists of decision problems solvable in polynomial time by a deterministic Turing machine. Polynomial-time algorithms are often regarded as efficiently solvable or tractable, though practical efficiency also depends on constants and lower-order terms. The concept contrasts with exponential time, where the bound grows as c^n or similar, which is typically infeasible for large n.

P is contained in NP, the class of problems solvable in polynomial time by a nondeterministic Turing machine, and whether P equals NP is one of the central open questions in computer science.

Common examples of polynomial-time problems include primality testing (now known to be in P via the AKS algorithm), sorting with comparison-based methods like mergesort (O(n log n)), many graph problems such as reachability, shortest paths, and flow algorithms, and various combinatorial problems when restricted.

Note that the notion of polynomial time depends on how the input is encoded; numbers or structures encoded in binary may yield different size measures than unary representations. Polynomial time is thus a standard benchmark for tractability, but the practical performance also hinges on constants and implementation details.