5
$\begingroup$

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?

$\endgroup$
  • 6
    $\begingroup$ Subset sum is certainly NP-Complete and none of the solutions you linked is even close to being polynomial time (which, by the way, is also explicitly stated in the article). I don't see what answer you would expect other than "no, they haven't". $\endgroup$ – quicksort Mar 5 '17 at 13:07
7
$\begingroup$

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.

$\endgroup$
6
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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