Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.
Sign up to join this community
I can not understand why the dynamic programming algorithm for the Subset Sum, is not polynomial.
Even though the sum to find 'T' is greater than the total sum of the 'n' elements of the set , the number of iterations is always (T * n) and not exponential I'm not understanding it.
The algorithm always do 'n*T' comparisons, and writes in the matrix only 'n*T' times...I'm missing something and I don't know what it is.
The reason is that you have to take into account the binary encoding of numbers. The input size $m$ is really the total number of bits, so if your instance is $a_1,\ldots, a_n, T$, then $m = \log T + \sum_{i\in [n]} \log a_i$.
In particular, $T$ can be super-polynomial in $m$, so the dynamic programming algorithm's runtime can be made super-polynomial as well, since it needs to take one step to build every cell of its table. (The quantity $nT$ can be made $\Omega(2^{m/3})$ for example.)
On the other hand, when all the numbers in the instance are restricted to be "small" (i.e., polynomially bounded in $m$), the SUBSET-SUM becomes tractable. (Notice that the usual reduction from 3SAT has very large numbers in it.)
A problem is strongly NP-Complete when it remains NP-Complete even when all the numeric values are polynomial in the input length. SUBSET-SUM isn't (it's called weakly NP-Complete).
The kind of running time that is polynomial in the numeric values in the input is known as pseudo-polynomial.
Another way to think about it which may be easier to understand: If we double $T$, we need one more bit to represent it, and $T$ is part of the input, so the input size increases by one bit. However, the run time doubles, and we can keep doing this and the run time will double each time while the input size will increase by one each time.
We measure the complexity of algorithms by considering the run time as a function of the input size, and in this example, the run time grows exponentially with respect to the input size, so we know that the run time cannot be polynomial.
The algorithm is exponential in the size of the input because of the assumption that integers are represented in binary. The running time is $O(T \cdot n)$, where $T$ is the integer (sum) and $n$ is the size of the set. Since $T$ is - typically and realistically - represented in binary, $T$ is represented by at least $O(log_2 T)$ bits*. So it takes $O(log_2 T)$ time to read this bit-vector sequentially. In the DP algorithm, you have to consider all values (sums) from $1$ to $T$ (assuming $T$ is positive); this is exponential in the length of $T$. To see this, note that:
$k = log_2 T$
$T = 2^{k}$
So if you have a bit-vector that is $b$ bits long, the largest number you can represent is approximately $2^b$; a number exponential in $b$.
Example
The maximum value of a $32$ bit signed integer is $T = 2^{31} - 1$. In order to read this bit-vector sequentially you have to read $32$ bits. But if you want to, say, make an array of length $T$, this would yield an array of length $T = 2^{31} - 1 = 2,147,483,647$. To construct the array would also take $T$ time.
Alternative representation
You could represent integers in unary, which means that the length of the representation of the integer is equal to the value of the integer. Then you could say that the running time of the algorithm is polynomial. But this is of course not an improvement. Algorithms like this, which are polynomial in the numeric value of the input, are said to run in pseudo-polynomial time.
* Typically, integers are stored in a fixed size representation, e.g. $32$ bits or $64$ bits. I also use big-oh notation to omit the details of how to exactly get the length of the representation of the integer, or the minimum length that would be needed in order to represent an integer in binary, since I feel that it might lead to a lot of details that don't help convey the overall idea.
