Editing Time complexity (section)

== Polynomial time ==
{{main|P (complexity)}}
An algorithm is said to be of '''polynomial time''' if its running time is [[upper bound]]ed by a [[polynomial]] expression in the size of the input for the algorithm, that is, {{nowrap|1=''T''(''n'') = ''O''(''n''<sup>''k''</sup>)}} for some positive constant ''k''.<ref name=Sipser>{{Cite book| last=Sipser | first=Michael | author-link=Michael Sipser | title=Introduction to the Theory of Computation | year=2006 | publisher=Course Technology Inc | isbn=0-619-21764-2 }}</ref><ref>{{Cite book| last=Papadimitriou | first=Christos H. | author-link=Christos H. Papadimitriou | title=Computational complexity | year=1994 | publisher=Addison-Wesley | location=Reading, Mass.  | isbn=0-201-53082-1 }}</ref> [[Decision problem|Problems]] for which a deterministic polynomial-time algorithm exists belong to the [[complexity class]] '''[[P (complexity)|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".<ref>{{Cite book| last=Cobham | first=Alan | author-link=Alan Cobham (mathematician) | year = 1965 | chapter = The intrinsic computational difficulty of functions | title = Proc. Logic, Methodology, and Philosophy of Science II | publisher = North Holland}}</ref>

Some examples of polynomial-time algorithms:
* The [[selection sort]] sorting algorithm on ''n'' integers performs <math>An^2</math> operations for some constant ''A''. Thus it runs in time <math>O(n^2)</math> and is a polynomial-time algorithm.
* All the basic arithmetic operations (addition, subtraction, multiplication, division, and comparison) can be done in polynomial time.
* [[Maximum matching]]s in [[Graph (discrete mathematics)|graphs]] can be found in polynomial time. In some contexts, especially in [[Optimization (mathematics)|optimization]], one differentiates between '''[[Strongly-polynomial time|strongly polynomial time]]''' and '''weakly polynomial time''' algorithms. 

These two concepts are only relevant if the inputs to the algorithms consist of integers.

=== Complexity classes ===

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 (complexity)|P]]''': The [[complexity class]] of [[decision problem]]s that can be solved on a [[deterministic Turing machine]] in polynomial time
* '''[[NP (complexity)|NP]]''': The complexity class of decision problems that can be solved on a [[non-deterministic Turing machine]] in polynomial time
* '''[[ZPP (complexity)|ZPP]]''': The complexity class of decision problems that can be solved with zero error on a [[probabilistic Turing machine]] in polynomial time
* '''[[RP (complexity)|RP]]''': The complexity class of decision problems that can be solved with 1-sided error on a probabilistic Turing machine in polynomial time.
* '''[[BPP (complexity)|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 [[Robustness (computer science)|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.