Pseudopolynomial
In complexity theory , an algorithm is called pseudopolynomial if its running time is a polynomial in the numerical value of the input.
example
We consider the problem of the primality test . That a given number n is a prime number can be checked by explicitly calculating that it cannot be evenly divided by any of the numbers . This requires n-2 divisions, which means that the running time of this naive algorithm is linear in n . However, this is not an efficient algorithm as one normally assumes from linear algorithms, because e.g. B. a 9-digit entry billions of divisions is required. Since, in complexity theory, the complexity of an algorithm is calculated based on the length of the input and the length ( assuming meaningful coding ) is logarithmically dependent on n , the algorithm described falls into the class of exponential running time.
The difference becomes clear when you compare this to a true polynomial algorithm such as B. the algorithm for adding numbers: adding two 9-digit numbers takes about 9 steps, i. that is, this algorithm is really polynomial in the length of the input.
Generalization to non-numeric problems
Although the term pseudopolynomial is used almost exclusively for numerical problems, the principle can be generalized: A function m is called pseudopolynomial if m (n) has at most one polynomial dependence on the problem size n and on an additional property k (n) of the input . Numerical problems arise from this as a special case in which k is the numerical value of the input.
The distinction between the value of a number and its length is a question of coding: If numeric inputs were coded unary , pseudopolynomial would coincide with polynomial .
literature
- Michael R. Garey , David S. Johnson : Computers and Intractability. A Guide to the Theory of NP Completeness. WH Freeman and Company, New York NY et al. 1979, ISBN 0-7167-1044-7 .