Polynomial time
From Wikipedia, the free encyclopedia
 |
This article needs additional citations for verification. Please help improve this article by adding reliable references (ideally, using inline citations). 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]
Contents |
[edit] 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]
In some context, especially in optimization, this notion of polynomial time is also called strongly polynomial time.
[edit] Weakly polynomial time
Some texts use the term weakly polynomial running time. This means that running time is polynomial not in the size of the input, but in the numerical value of the input, which may be exponentially larger than its (e.g., binary) representation. For example, the Euclidean Algorithm is only weakly polynomial when implemented using subtraction.
In contrast, strongly polynomial time means that the algorithm's running time depends only on the size of the input, regardless of the numerical values said input might represent. For example, an algorithm which could sort n integers each less than k in time O(n2) 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).
[edit] 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.) 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.
[edit] Examples
The quicksort sorting algorithm on n integers performs at most An2 operations for some constant A. Thus it runs in time O(n2) and is a polynomial time algorithm.
[edit] See also
- P (complexity)
- Constant time
- Linear time
- sub-exponential time
- Exponential time
- Complexity classes P and NP
[edit] References
- ^ Cobham, Alan (1965). "The intrinsic computational difficulty of functions". Proc. Logic, Methodology, and Philosophy of Science II. North Holland.
- ^ Papadimitriou, Christos H. (1994). Computational complexity. Reading, Mass.: Addison-Wesley. ISBN 0-201-53082-1.
- ^ Sipser, Michael (2006). Introduction to the Theory of Computation. Course Technology Inc. ISBN 0-619-21764-2.
