# Subset sum problem is NP-complete?

If I know correctly, subset sum problem is NP-complete. Here you have an array of n integers and you are given a target sum t, you have to return the numbers from the array which can sum up to the target (if possible).

But can't this problem be solved in polynomial time by dynamic programming method where we construct a table n X t and take cases like say last number is surely included in output and then the target becomes t- a[n]. In other case, the last number is not included, then the target remains same t but array becomes of size n-1. Hence this way we keep reducing size of problem.

If this approach is correct, isn't the complexity of this n * t, which is polynomial? and so if this belongs to P and also NP-complete (from what I hear) then P=NP.

Surely, I am missing something here. Where is the loophole in this reasoning?

Thanks,

-
The loophole is that input is smaller than you think. The dynamic programming method is pseudo-polynomial: it's polynomial in the values supplied as input, but the values are exponential in their length when represented in any base greater than 1. – Peter Taylor May 21 '11 at 7:56
t is exponential in the input size. With k digits of input you can represent numbers up to about 10^k (or 2^k or whatever). – ShreevatsaR May 21 '11 at 8:49
Not to put too fine a point on it, but your argument would also show that trial division is a polynomial-time factorization algorithm. Factoring $n$ by trial division is polynomial in $n$, but not in the length of $n$, which length is $\log n$, and it's the length of $n$ - the length of the input - that counts. – Gerry Myerson May 21 '11 at 11:05
Another issue is that you haven't formulated the problem as a decision problem (with a yes/no answer), but NP consists only of decision problems. Perhaps in the actual problem you intend to consider, the output should just be yes or no depending on whether there is such a subset, without needing to return the satisfying instance. This difference sometimes matters, since for example, testing primality is polynomial time, but we don't expect to be able to get factors in polynomial time. – JDH May 21 '11 at 12:00

If you express the inputs in unary you get a different running time than if you express them in a higher base (binary, most commonly).

So the question is, for subset sum, what base is appropriate? In computer science we normally default to the following:

• If the input is a list or collection, we express its size as the number of items
• If the input is an integer, we express its size as the number of bits (binary digits)

The intuition here is that we want to take the more "compact" representation.

So for subset sum, we have a list of size $n$ and a target integer of value $t$. Therefore it's common to express the input size as $n$ and $t=2^k$ where $k$ is the number of bits needed to express $t$. So the running time is $O(n 2^k)$ which is exponential in $k$.

But one could also say that $t$ is given in unary. Now the size of $t$ is $t$, and the running time is $O(n t)$, which is polynomial in $n$ and $t$.

In reductions involving subset sum (and other related problems like partition, 3-partition, etc) we must use a non-unary representation if we want to use it as an NP-Hard problem to reduce from.

-
Do you mean NP-Hard problem to reduce from? – Aryabhata May 21 '11 at 17:37
Yes, thanks. Corrected. – Fixee May 21 '11 at 19:35

This is one of those fine points sometimes neglected when learning about the subject. The efficiency of an algorithm is always measured in regards to the size of representation of the input - how much bits you need to encode it. In the case of numbers this distinction is crucial since the number $n$ is usually represented by $\lg n$ (log in the base 2) of bits. Hence, a solution that is $O(n)$ is exponential in the input size, hence extremely inefficient.

The classic example for this distinction is primality checking; even the most naive algorithm is $O(n)$, but we can't think of something like this as truly efficient even if we adopt a real-life approach - we can (and do) work with numbers with hundereds of digits on a daily basis, and usual arithmetic with those numbers is quite fast (being polynomial in the number of digits), but naive primality testing methods will never finish in real life even for numbers with a hundred digits or so.

The same danger lurks in any problem involving numbers, in particular subset sum.

-
Did you mean size of input, rather than output? – Aryabhata May 21 '11 at 16:48
Of course, silly me, thanks. The output is usually one bit... – Gadi A May 21 '11 at 16:56