In Complexity theory, **Polynomial time** refers to the computation time of a problem where the time, *m*(*n*), is no greater than a polynomial function of the problem size, *n*.

Written mathematically, *m*(*n*) = O(*n*^{k}) where *k* is a constant.

Mathematicians sometimes use the notion of "polynomial time on the length of the input" as a definition of a "fast" computation, as opposed to "super-polynomial time", which is anything slower than that. Exponential time is one example of a super-polynomial time.

The class of decision problems that can be solved on a deterministic sequential machine in polynomial time is known as **P**. The class of decision problems that can be verified in polynomial time is known as **NP**. Equivalently, NP is the class of decision problems that can be solved in
polynomial time on a Non-deterministic Turing machine (NP stands for
**N**ondeterministic **P**olynomial time).

See also: