What does psuedo-polynomial algorithm for subset sum problem mean?

Question

Help me out here - just trying to better understand what 'psuedo-polynomial' means...

If the input to an NP-Complete problem is 100 items(ie n=100), and the 'target' is the actual value '100'(t=100): Does a psuedo-polynomial algorithm take n*t (ie.. 100*100) steps to complete?

If so it seems to me that a psuedo-polynomial algorithm is much faster than exponential algorithm.

C

Answer 1

Yes, the pseudo-polynomial algorithm takes $O(nt)$ steps. However, this may not be faster than the exponential algorithm. Suppose $t\approx 2^n$? Then the algorithm takes $O(n2^n)$ steps, which is the same as the exponential algorithm, and it takes way more space.

Answer 2

Let's consider a simpler example. Let's consider an algorithm $A$ that takes an input $n$ and then counts up to $n$. How long does this take? Obviously, it takes time $O(n)$. Is $n$ a polynomial? Yes, but it is not a polynomial in the length of the input to $A$. The length of the numeral $n$ is only $\log n$, so time it takes to $A$ to count to $n$ is exponential in the size of the input.

The problem here is that numerals are very short compared with the numbers they represent. A big number like ten billion can be represented as an 11-digit numeral, and even a vast number like $10^{100}$ can be represented easily as a 101-digit numeral. Even though there are less than $10^{100}$ particles in the universe, you can write $10^{100}$ on a single paper in a minute.

A pseudo-polynomial algorithm is one whose inputs are numbers, and which runs in time that is a polynomial function of the largest of these numbers. But an algorithm that is polynomial in the size of the largest number is exponential in the length of the input, because numerals are so very compact.

You can solve subset-sum in time $nt$. But the length of the input in this case is only $\log n +\log t$, so this running time $nt$ is not a polynomial function of the length of the input.

The practical result of this is that for reasonable problem sizes, involving reasonable-size numbers, the straightforward dynamic programming algorithm solves subset-sum fast enough. But this is useless for solving NP-complete problems more generally. For suppose you have an instance of some problem like SAT with say 100 clauses. The reduction to subset-sum will result in a subset-sum instance with $n$ and $t$ about as long as the original SAT instance—in fact some polynomial function of this length. In the best case that polynomial function will be linear, so the $n$ and $t$ you get will have something like $100$ digits each. But that means that $n$ and $t$ themselves will be something like $10^{100}$. And even though $n$ in such a case is only $100$ digits long, there is not enough time in the universe to solve subset-sum in time $nt$ when $n$ or $t$ is on the order of $10^{100}$.