Take the 2-minute tour ×
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.

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.

share|improve this question

3 Answers 3

up vote 5 down vote accepted

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.

share|improve this answer
2  
The buzzword of note here is pseudo-polynomial time. One has to leave behind comfortable RAM models (with uniform costs) and really consider the TM model (with logarithmic cost model). –  Raphael May 7 at 11:15
    
Sorry for my stupidity but, what exactly turns to be exponential...in all problems instances coudl be very large too...I mean n*T could be large ¿and? I don't understand... –  Pedro May 7 at 12:44
    
For $nT$ to be polynomial in $m$, $T$ has to be polynomial in $m$. But since $T$ contributes only $\log T$ bits to $m$, this isn't necessarily true. For concreteness, consider the case where $T$ is an $m/2$ bit number and see what happens to the number of entries written in the matrix. –  Louis May 7 at 13:06
2  
What you are missing is that a $k$-bit number can be as large as $2^k - 1$. –  Louis May 7 at 13:33
1  
@Raphael I'm not sure the term pseudo-polynomial qualifies as a buzzword ... –  Pål GD May 7 at 17:12

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.

share|improve this answer

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.

share|improve this answer
    
So the problem is only the array, isn't it? Becouse the memory it consumed...Is that? I don't think that are the sum from 1 to T, becouse that's polinomial, isn't it? –  Pedro May 7 at 15:43
    
@Pedro I don't think I understand what you mean. It is not important if what we are doing is to construct an array, or if we are looping; the point is in the fact that we have to iterate from $1$ to $T$, while $T$ is given to us as a bit-vector (so if $T$ is represented as $32$ bits, $T$ might be as large as $2^{31} - 1$, which means we have to iterate from $1$ to $2^{31} - 1$. –  Guildenstern May 7 at 16:08
    
For that matter; if you have, say, a DP algorithm that constructs and array of size $T$ and iterates through it in order to solve some problem, that would mean that the space complexity of the algorithm is $O(T)$. Maybe it was the distinction between space complexity and run time complexity that you were getting at? –  Guildenstern May 7 at 16:13
    
Oh...so If we iterate in a For...next from 1 to N , we are really iterating from 1 to 2^31? –  Pedro May 7 at 16:15
    
^ Yes, if $N = 2^{31}$. Meanwhile, $N$ is represented by only $32$ bits. –  Guildenstern May 7 at 16:16

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.