How is the Subset Sum Problem NP-Complete?

Question

You can't find a solution online for it that doesn't run in polynomial time complexity, when using dynamic programming. Have all these sites secretly solved P=NP, and no one knows about it?

Answer 1

The dynamic programming approaches only solve the problem in pseudopolynomial time.

Recall that the definition of (nondeterministic) polynomial time is that the problem must be solvable by a (nondeterministic) Turing machine whose running time is bounded by some polynomial in the size of the input. The size of the input is the number of bits required to write it down.

Suppose we want to solve a subset sum instance where the set has size $k$ (i.e., contains $k$ integers), and suppose this takes $n$ bits to write down. The dynamic programming approach builds up a table with $k$ rows and one column for each possible partial sum. How big is this table? Well, surely $k\leq n$, since we can't write down more than $n$ numbers in only $n$ bits. However, a partial sum is the sum of some number of integers, each of which takes about $n/k$ bits to write down. So that sum is also going to take roughly $n/k$ bits to write down. That means that there are roughly $2^{n/k}$ columns in our table, so our table is exponentially large and we can't populate it in polynomial time.

The algorithm runs in pseudopolynomial time, which means that it runs in time bounded by some polynomial in the numbers represented in the instance, rather than in the number of bits required to write them down.

(In fact, this dynamic programming approach uses even more memory than doing dynamic programming on subsets. Suppose, for example, that your set is $\{1,100\}$. There are only three nonempty subsets but you're likely to decide that a partial sum could be anywhere between $0$ and $101$, giving a table with two rows and $101$ columns, instead of two rows and three columns.

Answer 2

There are indeed no polynomial time algorithms to solve subset-sum, but there are pseudo-polynomial time algorithms. What does this mean ? That their running time is polynomial in the numeric values, but exponential in the length of the input, because that is logarithmic in the numeric values ( binary representations, and not unary ).

That is by the way the difference between strong and week NP-completeness.

Answer 3

The subset sum problem can easily be solved in polynomial time in the number of items, and the sizes of the items. However, to be in NP, the solution must be in polynomial time in the problem size. Say all items are <= 9999, then I only need 4 digits to write down a number. If all items are less than a billion billion billions, then I need only 27 digits to write down each item size. 1000 such items, there are solutions in polynomial time in 1000 and a billion billion billions. NP wants polynomial time in 1000 and 27.