Editing Time complexity (section)

=== 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.