Polynomial time

This article needs additional citations for verification. Please help improve this article by adding reliable references. Unsourced material may be challenged and removed. (February 2009)

In computer science, polynomial time refers to the running time of an algorithm, that is, the number of computation steps a computer or an abstract machine requires to evaluate the algorithm. An algorithm is said to be polynomial time if its running time is upper bounded by a polynomial in the size of the input for the algorithm. Problems for which a polynomial time algorithm exists belong to the complexity class PTIME, 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".^[1]

Formal definition

More formally, let T(n) be the running time of the algorithm on inputs of size at most n. Then the algorithm is polynomial time if there exists a polynomial p(n) such that, for all input sizes n, the running time T(n) is no larger than p(n).^[2][3]

Strongly and weakly polynomial time

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 ^[4]

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 requirement above is omitted, then this is not true any more. Given n integers it is possible to compute with n multiplications using repeated squaring. If the integers are small enough (say they are equal to 1), then cannot be represented in polynomial space. Hence, it is not possible to compute this number in polynomial time on a Turing machine, but it is possible to compute it by polynomially many arithmetic operations.

There are algorithms which run in polynomial time in the Turing machine model but not in the arithmetic model. The Euclidean algorithm for computing the greatest common divisor of two integers is one example. Given two integers a and b the running time of the algorithm is bounded by . This is polynomial in the size of a binary representation of a and b as the size of such a representation is roughly . However, the algorithm does not run in strongly polynomial time as the running time depends on the magnitudes of a and b and not only on the number of integers in the input (which is constant in this case, there is always only two integers in the input).

An algorithm which runs in polynomial time but which is not strongly polynomial is said to run in weakly polynomial time.^[5] 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 classes

The complexity class of decision problems that can be solved on a deterministic sequential machine in polynomial time is known as P. 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.) Any given abstract machine will have a complexity class corresponding to the problems which can be solved in polynomial time on that machine.

Examples

• 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.
• All the basic arithmetic operations (addition, subtraction, multiplication, division, and comparision) can be done in polynomial time.
• Maximum matchings in graphs can be found in polynomial time.

See also

• P (complexity)
• Constant time
• Linear time
• sub-exponential time
• Exponential time
• Complexity classes P and NP
• Big O notation

References