Pseudo-polynomial time

From Wikipedia, the free encyclopedia

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

1 An Example
2 Ramifications
3 Generalizing to non-numeric problems
4 References

[edit] An Example

Consider the problem of testing whether a number n is prime, by naively checking whether no number in {2,3,...,n-1} divides n evenly. This requires up to n-2 divisions, which is indeed linear in n. But this is certainly not an efficient algorithm: a 9-digit number requires billions of divisions; moreover one can easily write down an input (say, a 300-digit number) for which this algorithm is impractical. Since computational complexity measures difficulty as the length of its (encoded) input, this naive algorithm is actually exponential, even though it is pseudo-polynomial time.

Contrast this algorithm with a true polynomial numeric algorithm -- say, the straightforward algorithm for addition: Adding two 9-digit numbers takes around 9 simple steps, and in general the algorithm is truly linear in the length of the input. Compared with the actual numbers being added (in the billions), the algorithm could be called "pseudo-logarithmic time", though such a term is not standard. Thus, adding 300-digit numbers is not impractical. Similarly, long division is quadratic: an m-digit number can be divided by a n-digit number in $O (m n)$ steps (see Big O notation.)

In the case of primality, it turns out there is a different algorithm for testing whether n is prime (discovered in 2002) which runs in time $O (log 6 n)$ .

[edit] Ramifications

If a problem is in P, then it per force has a pseudo-polynomial time algorithm. But NP-Complete problems may also have pseudo-polynomial time algorithms (for example, the Knapsack problem). Garey and Johnson write:

A pseudo-polynomial-time algorithm … will display 'exponential behavior' only when confronted with instances containing 'exponentially large' numbers, [which] might be rare for the application we are interested in. If so, this type of algorithm might serve our purposes almost as well as a polynomial time algorithm.

(where by "exponentially large numbers", they mean "numbers with many digits").

[edit] Generalizing to non-numeric problems

Although the notion of pseudo-polynomial time is used almost exclusively for numeric problems, the concept can be generalized: The function m is pseudo-polynomial if m(n) is no greater than a polynomial function of the problem size n and an additional property of the input, k(n). (Presumably, k is chosen to be something relevant to the problem.) This makes numeric problems a special case by taking k to be the number of (binary) digits of the input.

The distinction betweeen the value of a number and its length is one of encoding: if numeric inputs are always encoded in unary, then pseudo-polynomial would coincide with polynomial.