Polynomial time

An algorithm is said to be of polynomial time if its running time is upper bounded by a polynomial expression in the size of the input for the algorithm, i.e., T(n) = O(nk) for some positive constant k. Problems for which a deterministic polynomial time algorithm exists belong to the complexity class P, which is central in the field of computational complexity theory. Cobham's thesis states that polynomial time is a synonym for "tractable", "feasible", "efficient", or "fast".

Some examples of polynomial time algorithms:

• The selection sort sorting algorithm on n integers performs ${\displaystyle A{n}^2}$ operations for some constant A. Thus it runs in time ${\displaystyle O(n^2)}$ and is a polynomial time algorithm.
• All the basic arithmetic operations (addition, subtraction, multiplication, division, and comparison) can be done in polynomial time.
• Maximum matchings in graphs can be found in polynomial time.

Strongly and weakly polynomial timeedit

In some contexts, especially in optimization, one differentiates between strongly polynomial time and weakly polynomial time algorithms. These two concepts are only relevant if the inputs to the algorithms consist of integers.

Strongly polynomial time is defined in the arithmetic model of computation. In this model of computation the basic arithmetic operations (addition, subtraction, multiplication, division, and comparison) take a unit time step to perform, regardless of the sizes of the operands. The algorithm runs in strongly polynomial time if

1. the number of operations in the arithmetic model of computation is bounded by a polynomial in the number of integers in the input instance; and
2. the space used by the algorithm is bounded by a polynomial in the size of the input.

Any algorithm with these two properties can be converted to a polynomial time algorithm by replacing the arithmetic operations by suitable algorithms for performing the arithmetic operations on a Turing machine. If the second of the above requirements is not met, then this is not true anymore. Given the integer ${\displaystyle 2^n}$ (which takes up space proportional to n in the Turing machine model), it is possible to compute ${\displaystyle 2^{2^n}}$ with n multiplications using repeated squaring. However, the space used to represent ${\displaystyle 2^{2^n}}$ is proportional to ${\displaystyle 2^n}$, and thus exponential rather than polynomial in the space used to represent the input. Hence, it is not possible to carry out this computation in polynomial time on a Turing machine, but it is possible to compute it by polynomially many arithmetic operations.

Conversely, there are algorithms that run in a number of Turing machine steps bounded by a polynomial in the length of binary-encoded input, but do not take a number of arithmetic operations bounded by a polynomial in the number of input numbers. The Euclidean algorithm for computing the greatest common divisor of two integers is one example. Given two integers ${\displaystyle a}$ and ${\displaystyle b}$, the algorithm performs ${\displaystyle O(\log <!--\; \; -->a+\log <!--\; \; -->b)}$ arithmetic operations on numbers with at most ${\displaystyle O(\log <!--\; \; -->a+\log <!--\; \; -->b)}$ bits. At the same time, the number of arithmetic operations cannot be bounded by the number of integers in the input (which is constant in this case, there are always only two integers in the input). Due to the latter observation, the algorithm does not run in strongly polynomial time. Its real running time depends on the magnitudes of ${\displaystyle a}$ and ${\displaystyle b}$ and not only on the number of integers in the input.

An algorithm that runs in polynomial time but that is not strongly polynomial is said to run in weakly polynomial time. A well-known example of a problem for which a weakly polynomial-time algorithm is known, but is not known to admit a strongly polynomial-time algorithm, is linear programming. Weakly-polynomial time should not be confused with pseudo-polynomial time.

Complexity classesedit

The concept of polynomial time leads to several complexity classes in computational complexity theory. Some important classes defined using polynomial time are the following.

P	The complexity class of decision problems that can be solved on a deterministic Turing machine in polynomial time
NP	The complexity class of decision problems that can be solved on a non-deterministic Turing machine in polynomial time
ZPP	The complexity class of decision problems that can be solved with zero error on a probabilistic Turing machine in polynomial time
RP	The complexity class of decision problems that can be solved with 1-sided error on a probabilistic Turing machine in polynomial time.
BPP	The complexity class of decision problems that can be solved with 2-sided error on a probabilistic Turing machine in polynomial time
BQP	The complexity class of decision problems that can be solved with 2-sided error on a quantum Turing machine in 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.) Any given abstract machine will have a complexity class corresponding to the problems which can be solved in polynomial time on that machine.