Encyclopedia > Polynomial time

  Article Content

Polynomial time

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(nk) 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 Nondeterministic Polynomial time).

See also:



All Wikipedia text is available under the terms of the GNU Free Documentation License

 
  Search Encyclopedia

Search over one million articles, find something about almost anything!
 
 
  
  Featured Article
Northampton, Suffolk County, New York

... census of 2000, there are 468 people, 158 households, and 121 families residing in the town. The population density is 19.9/km² (51.6/mi²). There are 205 ...

 
 
 
This page was created in 25.6 ms