Pseudo-polynomial time

In complexity theory, an algorithm is called pseudopolynomiell if its running time is a polynomial in the numeric value of the input.

Example

We consider the problem of primality testing. The fact that a given number n is prime, it can be checked by explicitly recalculate that it can be divided by any of the numbers smooth. This requires n-2 divisions, whereby the duration of this naive algorithm is linear in n. Nevertheless, this is not an efficient algorithm, as one of linear algorithms usually assumes, because a 9- digit entry already requires billions of divisions, for example. Since the computational complexity, the complexity of an algorithm is calculated based on the length of the entry, and the length ( a "meaningful" encoding) logarithmically dependent on n, the described algorithm falls into the class exponential term.

The difference becomes clear when one compares this with a real polynomial algorithm, such as the algorithm for addition of numbers: The addition of two 9- digit numbers requires about 9 steps, ie, this algorithm is actually polynomial in the length the input.

Generalization to non-numeric problems

Although the term is pseudopolynomiell almost exclusively used for numerical problems, the principle can be generalized: We call a function m pseudopolynomiell, if m (n ) is at most a polynomial function of the problem size n and by an additional property k (n ) of the input has. Numerical problems arise from this as a special case in which k is the number of ( binary ) digits is entered.

The distinction between the value of a number and its length is a matter of coding: Would numeric entries unary coded so would pseudopolynomiell coincide with polynomially.