[Solved]: Can't understand why the DP Subset Sum algorithm is not polynomial

Problem Detail: 

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.

Asked By : Pedro

Answered By : Louis

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

NP-C problems that remain NP-C when all the numeric values are polynomial in the input length are called strongly NP-C. SUBSET-SUM isn't (it's called weakly NP-C).

The kind of running time that is polynomial in the numeric values in the input is known as pseudo-polynomial.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/24484