What is pseudopolynomial time? How does it differ from polynomial time?

Question

What is pseudopolynomial time? How does it differ from polynomial time? Some algorithms that run in pseudopolynomial time have runtimes like O(nW) (for the 0/1 Knapsack Problem) or O(√n) (for trial division); why doesn't that count as polynomial time?

Answer 1

To understand the difference between polynomial time and pseudopolynomial time, we need to start off by formalizing what "polynomial time" means.

The common intuition for polynomial time is "time O(n^k) for some k." For example, selection sort runs in time O(n²), which is polynomial time, while brute-force solving TSP takes time O(n · n!), which isn't polynomial time.

These runtimes all refer to some variable n that tracks the size of the input. For example, in selection sort, n refers to the number of elements in the array, while in TSP n refers to the number of nodes in the graph. In order to standardize the definition of what "n" actually means in this context, the formal definition of time complexity defines the "size" of a problem as follows:

The size of the input to a problem is the number of bits required to write out that input.

For example, if the input to a sorting algorithm is an array of 32-bit integers, then the size of the input would be 32n, where n is the number of entries in the array. In a graph with n nodes and m edges, the input might be specified as a list of all the nodes followed by a list of all the edges, which would require Ω(n + m) bits.

Given this definition, the formal definition of polynomial time is the following:

An algorithm runs in polynomial time if its runtime is O(x^k) for some constant k, where x denotes the number of bits of input given to the algorithm.

When working with algorithms that process graphs, lists, trees, etc., this definition more or less agrees with the conventional definition. For example, suppose you have a sorting algorithm that sorts arrays of 32-bit integers. If you use something like selection sort to do this, the runtime, as a function of the number of input elements in the array, will be O(n²). But how does n, the number of elements in the input array, correspond to the the number of bits of input? As mentioned earlier, the number of bits of input will be x = 32n. Therefore, if we express the runtime of the algorithm in terms of x rather than n, we get that the runtime is O(x²), and so the algorithm runs in polynomial time.

Similarly, suppose that you do depth-first search on a graph, which takes time O(m + n), where m is the number of edges in the graph and n is the number of nodes. How does this relate to the number of bits of input given? Well, if we assume that the input is specified as an adjacency list (a list of all the nodes and edges), then as mentioned earlier the number of input bits will be x = Ω(m + n). Therefore, the runtime will be O(x), so the algorithm runs in polynomial time.

Things break down, however, when we start talking about algorithms that operate on numbers. Let's consider the problem of testing whether a number is prime or not. Given a number n, you can test if n is prime using the following algorithm:

function isPrime(n):
    for i from 2 to n - 1:
        if (n mod i) = 0, return false
    return true

So what's the time complexity of this code? Well, that inner loop runs O(n) times and each time does some amount of work to compute n mod i (as a really conservative upper bound, this can certainly be done in time O(n³)). Therefore, this overall algorithm runs in time O(n⁴) and possibly a lot faster.

In 2004, three computer scientists published a paper called PRIMES is in P giving a polynomial-time algorithm for testing whether a number is prime. It was considered a landmark result. So what's the big deal? Don't we already have a polynomial-time algorithm for this, namely the one above?

Unfortunately, we don't. Remember, the formal definition of time complexity talks about the complexity of the algorithm as a function of the number of bits of input. Our algorithm runs in time O(n⁴), but what is that as a function of the number of input bits? Well, writing out the number n takes O(log n) bits. Therefore, if we let x be the number of bits required to write out the input n, the runtime of this algorithm is actually O(2^4x), which is not a polynomial in x.

This is the heart of the distinction between polynomial time and pseudopolynomial time. On the one hand, our algorithm is O(n⁴), which looks like a polynomial, but on the other hand, under the formal definition of polynomial time, it's not polynomial-time.

To get an intuition for why the algorithm isn't a polynomial-time algorithm, think about the following. Suppose I want the algorithm to have to do a lot of work. If I write out an input like this:

10001010101011

then it will take some worst-case amount of time, say T, to complete. If I now add a single bit to the end of the number, like this:

100010101010111

The runtime will now (in the worst case) be 2T. I can double the amount of work the algorithm does just by adding one more bit!

An algorithm runs in pseudopolynomial time if the runtime is some polynomial in the numeric value of the input, rather than in the number of bits required to represent it. Our prime testing algorithm is a pseudopolynomial time algorithm, since it runs in time O(n⁴), but it's not a polynomial-time algorithm because as a function of the number of bits x required to write out the input, the runtime is O(2^4x). The reason that the "PRIMES is in P" paper was so significant was that its runtime was (roughly) O(log¹² n), which as a function of the number of bits is O(x¹²).

So why does this matter? Well, we have many pseudopolynomial time algorithms for factoring integers. However, these algorithms are, technically speaking, exponential-time algorithms. This is very useful for cryptography: if you want to use RSA encryption, you need to be able to trust that we can't factor numbers easily. By increasing the number of bits in the numbers to a huge value (say, 1024 bits), you can make the amount of time that the pseudopolynomial-time factoring algorithm must take get so large that it would be completely and utterly infeasible to factor the numbers. If, on the other hand, we can find a polynomial-time factoring algorithm, this isn't necessarily the case. Adding in more bits may cause the work to grow by a lot, but the growth will only be polynomial growth, not exponential growth.

That said, in many cases pseudopolynomial time algorithms are perfectly fine because the size of the numbers won't be too large. For example, counting sort has runtime O(n + U), where U is the largest number in the array. This is pseudopolynomial time (because the numeric value of U requires O(log U) bits to write out, so the runtime is exponential in the input size). If we artificially constrain U so that U isn't too large (say, if we let U be 2), then the runtime is O(n), which actually is polynomial time. This is how radix sort works: by processing the numbers one bit at a time, the runtime of each round is O(n), so the overall runtime is O(n log U). This actually is polynomial time, because writing out n numbers to sort uses Ω(n) bits and the value of log U is directly proportional to the number of bits required to write out the maximum value in the array.

Hope this helps!