Polynomial time

In computational 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'') = Big O notation(''n''^''k'') where ''k'' is a constant (which may depend on the problem). 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 complexity class of decision problems that can be solved on a deterministic sequential machine in polynomial time is known as P (complexity). The class of decision problems that can be verified in polynomial time is known as NP (complexity). 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). == Subclasses of polynomial time == * Linear time: Big O notation(''n'') * Quadratic time: Big O notation(''n''²) * Cubic time: Big O notation(''n''³) == See also == *Computational complexity theory *Exponential time *Complexity classes P and NP *NP (complexity) *Algorithm *Big O notation Complexity classes

See other meanings of words starting from letter:

P

PA | PB | PC | PD | PE | PF | PG | PH | PI | PJ | PK | PL | PM | PN | PO | PR | PS | PT | PU | PW | PX | PY | PZ |

Words begining with Polynomial_time:

Polynomial-time
Polynomial-time_approximation_scheme
Polynomial-time_many-one_reduction
Polynomial-time_reduction
Polynomial-time_Turing_reduction
Polynomial_time
Polynomial_time_approximation_scheme