Time complexity#Polynomial time

In complexity theory, we describe a problem as solvable in polynomial time when the required computing time of a deterministic computing machine with the problem size no greater than a polynomial function grows. The special significance of the polynomial is that they are viewed as a boundary between practical detachable and practically unsolvable problems. The cost of problems that are solvable in polynomial time not, generally grows so fast that even relatively small problem sizes with available computers can not be solved in reasonable time periods. This fact is independent of the technological progress, insofar as it relates to the speed of deterministic computer. A special position is occupied by the quantum computer, as it allows certain non- deterministic operations.

Whether a given problem is solvable in polynomial time, it is not clear from the outset. Thus, an algorithm ( AKS primality test ) was only in 2002 by Agrawal, Kayal and Saxena stated that decides in polynomial time whether a given natural number is prime or not. The natural method, simply try out all possible divisor is not polynomial.

Formal definition

A problem is solvable in polynomial time called when it is solved by an algorithm whose required computation time (eg, measured as the number of bit operations of a matching algorithm on a Turing machine ) is at most polynomially with the size of the input of the problem ( z. example, measured in number of bits ) is growing, that is, there is a natural number constant with according to the Landau notation.

Polynomial-time algorithm - an example

A simple method for sorting an array is the constant finding and deleting the largest of the elements present. The expense of this process is a square, because each element of the input maximum of all the other elements have to be considered once again. Since a quadratic function of the input is also polynomial, is a polynomial-time algorithm.

Superpolynomialzeit

Problems whose computation time more than a polynomial function grows with the problem size, soluble in hot Superpolynomialzeit; An example of this is exponential time constant that is, with.

Related to the complexity classes

The class of all problems that can be solved on a deterministic sequential machine in polynomial time is denoted as P (of polynomial ). The class of all problems that can be solved by a (hypothetical) non-deterministic machine in polynomial time is called NP (of nondeterministic polynomial - time). It is clear that, in other words, P is a subset of NP. An up today unproved conjecture is that both classes are really different, so that the following holds. The P- NP problem is the most important open problem in theoretical computer science.

Criticism

The polynomial has been viewed in the 1970s as the boundary between the practical and the detachable practically unsolvable problems. However, this distinction is not clear-cut in practice. On the one hand, there are also methods with exponential worst-case running time that can be used in practice; An example of this is the simplex algorithm. On the other hand, grow polynomials of higher degree already so fast that many running in polynomial time algorithms for practically existing problem sizes are not yet handled.

However, there is a number of reasons for the retention of the polynomial as a " limit of feasibility ." In particular, it has been found that many problems that a long time only with poor (high grade ) polynomial effort were solvable, each very soon also low polynomiellem effort could be solved ( approximately grade 2 or 3).