From Wikipedia, the free encyclopedia

In computational complexity theory, polynomial time refers to the computation time of a problem where the run time, m(n), is no greater than a polynomial function of the problem size, n. Written mathematically using big O notation, this states that m(n) = O(n^k) where k is some constant that may depend on the problem. For example, the quicksort sorting algorithm on n integers performs at most An² operations for some constant A. Thus it runs in time O(n²) and is a polynomial time algorithm.

Mathematicians sometimes use the notion of "polynomial time on the length of the input" as a definition of a "fast" or "feasible" computation (see Cobham's thesis), as opposed to "super-polynomial time", which is anything slower than that. Exponential time is one example of a super-polynomial time.

The complexity class of decision problems that can be solved on a deterministic sequential machine in polynomial time is known as P. The class of decision problems that can be verified in polynomial time is known as NP. Equivalently, NP is the class of decision problems that can be solved in polynomial time on a non-deterministic Turing machine (NP stands for Nondeterministic Polynomial time).

P is the smallest time-complexity class on a deterministic machine which is robust in terms of machine model changes. (For example, a change from a single-tape Turing machine to a multi-tape machine can lead to a quadratic speedup, but any algorithm that runs in polynomial time under one model also does so on the other.) P is also the smallest class closed under composition of subproblems. Any given abstract machine will have a complexity class corresponding to the problems which can be solved in polynomial time on that machine.

Some texts use the term weakly polynomial run time. This means that run time is polynomial not in the size of the input, but in the numerical value of the input, which may be exponentially larger. For example, the Euclidean Algorithm is only weakly polynomial when implemented using subtraction.

Similarly, running in strongly polynomial time means that the algorithm's run time is independent of the numerical data size and depends only on the inherent dimensions of the problem. For example, an algorithm which could sort n integers each less than k in time O(n²) would be strongly polynomial, while an algorithm sorting them in time O(nk) would be weakly polynomial (because an integer less than k can be represented in size logarithmic in k).

• Christos Papadimitriou (1994). Computational Complexity. Addison Wesley. 

• Constant time
• Linear time
• Complexity classes P and NP