Polynomial time

Polynomial time

In computational complexity theory, polynomial time refers to the computation time of a problem where the run time, "m"("n"), is no greater than a polynomial function of the problem size, "n".Written mathematically using big O notation, this states that m(n) = O(n^k) where "k" is some constant that may depend on the problem. For example, the quicksort sorting algorithm on "n" integers performs at most An^2 operations for some constant A. Thus it runs in time O(n^2) and is a polynomial time algorithm.

Mathematicians sometimes use the notion of "polynomial time on the length of the input" as a definition of a "fast" or "feasible" computation (see Cobham's thesis), as opposed to sub-exponential time (also super-polynomial time), which is anything slower than that. Exponential time is one example of a sub-exponential time.

The complexity 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).

P is the smallest time-complexity class on a deterministic machine which is 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.) P is also the smallest class closed under composition of subproblems. Any given abstract machine will have a complexity class corresponding to the problems which can be solved in polynomial time on that machine.

Some texts use the term weakly polynomial run time. This means that run time is polynomial not in the size of the input, but in the numerical value of the input, which may be exponentially larger. For example, the Euclidean Algorithm is only weakly polynomial when implemented using subtraction.

Similarly, running in strongly polynomial time means that the algorithm's run time is independent of the numerical data size and depends only on the inherent dimensions of the problem. For example, an algorithm which could sort "n" integers each less than "k" in time O(n^2) would be strongly polynomial, while an algorithm sorting them in time O(nk) would be weakly polynomial (because an integer less than "k" can be represented in size logarithmic in "k").

See also

*Constant time
*Linear time
*Complexity classes P and NP

References

*


Wikimedia Foundation. 2010.

Игры ⚽ Поможем написать реферат

Look at other dictionaries:

  • polynomial time — 1. noun time complexity which is bounded by some polynomial 2. adjective (Of an algorithm) which enjoys polynomial time …   Wiktionary

  • Polynomial-time approximation scheme — In computer science, a polynomial time approximation scheme (abbreviated PTAS) is a type of approximation algorithm for optimization problems (most often, NP hard optimization problems).A PTAS is an algorithm which takes an instance of an… …   Wikipedia

  • Polynomial-time reduction — In computational complexity theory a polynomial time reduction is a reduction which is computable by a deterministic Turing machine in polynomial time. If it is a many one reduction, it is called a polynomial time many one reduction, polynomial… …   Wikipedia

  • polynomial time — …   Useful english dictionary

  • Pseudo-polynomial time — In computational complexity theory, a numeric algorithm runs in pseudo polynomial time if its running time is polynomial in the numeric value of the input (which is exponential in the length of the input its number of digits).An ExampleConsider… …   Wikipedia

  • Almost Wide Probabilistic Polynomial-Time — In theoretical computer science, Almost Wide Probabilistic Polynomial Time (AWPP) is a complexity class for problems in the context of quantum computing.AWPP contains the BQP (Bounded error, Quantum, Polynomial time) class, which contains the… …   Wikipedia

  • Time complexity — In computer science, the time complexity of an algorithm quantifies the amount of time taken by an algorithm to run as a function of the size of the input to the problem. The time complexity of an algorithm is commonly expressed using big O… …   Wikipedia

  • Polynomial hierarchy — In computational complexity theory, the polynomial hierarchy is a hierarchy of complexity classes that generalize the classes P, NP and co NP to oracle machines.DefinitionsThere are multiple equivalent definitions of the classes of the polynomial …   Wikipedia

  • Polynomial — In mathematics, a polynomial (from Greek poly, many and medieval Latin binomium, binomial [1] [2] [3], the word has been introduced, in Latin, by Franciscus Vieta[4]) is an expression of finite length constructed from variables (also known as… …   Wikipedia

  • Polynomial space — In computational complexity theory, polynomial space refers to the space required in computation of a problem where the space, m ( n ), is no greater than a polynomial function of the problem size, n .Written mathematically, m ( n ) = O( n k )… …   Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”