1
$\begingroup$

The Subset-Sum decision problem is:

Given a set of n non-negative integers S, is there a subset of S that sum to k? If S and k are inputs, the problem is known to be NP-Complete.

What about the case when k is not an input but a constant?
Is the problem still NP-Complete?

My thoughts are that if k is given, since the integers are all non-negative, we only need to consider subsets of at most k elements (ignoring elements that are zero). That means we only need to consider at most $n^k$ possibilities which is polynomial. So, the problem is not NP-Complete. Is my understanding correct?

$\endgroup$
1
$\begingroup$

Yes. Even better, there is a dynamical programming solution that uses $O(nk)$ steps.

$\endgroup$
1
$\begingroup$

Commenting here for posterity, as this result is high in the search results for subset-sum. Subset-sum is absolutely NP-complete.

The missing information here is that $O(n^k)$ and $O(nk)$ are both exponential runtimes. The definition of NP-complete specifies runtimes in terms of the number of bits in the input, not in terms of single integer inputs like $k$.

Note that it requires $\log k$ bits to specify $k$. Therefore if you 'spend' n bits on the array input and m bits on specifying $k$, the runtime is $O(nk) = O(n2^m)$.

$\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.