Pseudo-polynomial time

Consider the problem of testing whether a number n is prime, by naively checking whether no number in ${\displaystyle \{2,3,\dots ,{\sqrt {n}}\}}$ divides ${\displaystyle n}$ evenly. This approach can take up to ${\displaystyle {\sqrt {n}}-1}$ divisions, which is sub-linear in the value of n but exponential in the length of n (which is about ${\displaystyle \log(n)}$). For example, a number n slightly less than 10,000,000,000 would require up to approximately 100,000 divisions, even though the length of n is only 11 digits. Moreover one can easily write down an input (say, a 300-digit number) for which this algorithm is impractical. Since computational complexity measures difficulty with respect to the length of the (encoded) input, this naive algorithm is actually exponential. It is, however, 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 ${\displaystyle O(mn)}$ 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) that runs in time ${\displaystyle O((\log {n})^{6})}$.

In the knapsack problem, we are given ${\displaystyle n}$ items with weight ${\displaystyle w_{i}}$ and value ${\displaystyle v_{i}}$, along with a maximum weight capacity of a knapsack ${\displaystyle W}$. The goal is to solve the following optimization problem; informally, what's the best way to fit the items into the knapsack to maximize value?

maximize ${\displaystyle \sum _{i=1}^{n}v_{i}x_{i}}$

subject to ${\displaystyle \sum _{i=1}^{n}w_{i}x_{i}\leq W}$ and ${\displaystyle x_{i}\in \{0,1\}}$.

Solving this problem is NP-hard, so a polynomial time algorithm is impossible unless P = NP. However, an ${\displaystyle O(nW)}$ time algorithm is possible using dynamic programming; since the number ${\displaystyle W}$ only needs ${\displaystyle \log W}$ bits to describe, this algorithm runs in pseudo-polynomial time.