1
$\begingroup$

I recognize that the subset sum problem is NP-Complete. I have a different, yet similar problem, which I'll call subset below-sum:

  • Given a set of integers, $S$, and a target number, $n$, what is the number of subsets of $S$ that sum to less than $n$?

For example, if $S$ is $\{1, 2, 3, 7, 7, 15\}$, and $n$ is $20$, the answer is $38$.

Is this an NP-Complete problem? If not, what is a fast algorithm to compute the answer?

Improve this question
$\endgroup$
2
  • $\begingroup$ There is no fast algorithm, unless P=NP. $\endgroup$
    – Yuval Filmus
    Jan 30 '16 at 0:36
  • $\begingroup$ A counting problem can never be in NP, by definition. $\endgroup$
    – Raphael ♦
    Jan 30 '16 at 13:10
2
$\begingroup$

Subset below-sum appears to be NP-Hard. This is informal, but consider, if you can solve subset below-sum in polynomial time, you can solve subset sum in polynomial time.

  • Given: does any subset of $S$ sum to exactly $n$?
  • Let $A$ be $subset\_below\_sum(n)$ and $B$ be $subset\_below\_sum(n + 1)$. If $B - A \gt 0$, the answer is yes, otherwise, the answer is no.
Improve this answer
$\endgroup$
2
  • $\begingroup$ This doesn't show that the problem is NP-hard. It only shows that it's not in P unless P=NP. It could be #P-hard, though. $\endgroup$
    – Yuval Filmus
    Jan 30 '16 at 0:35
  • $\begingroup$ @YuvalFilmus : ​ ​ ​ It also shows that it's NP-hard under non-adaptive 2-query reductions. ​ (Although your other sentences are correct.) ​ ​ ​ ​ ​ ​ ​ ​ $\endgroup$
    – user12859
    Jan 30 '16 at 1:29
0
$\begingroup$

The similar problem #Subset-Sum, in which we want to count the number of subsets summing to some target, is #P-complete (this is implied by this paper). This hints that your problem, which is clearly in #P, might also be #P-complete.

Improve this answer
$\endgroup$
6
  • $\begingroup$ Can you explain the correspondence? For instance, suppose $n=18$, so your plan is to add 16 to the set. Why does a subset summing to $17$ in the new set correspond to a subset summing to at most $17$ in the original set? For instance, consider a subset summing to 15 in the original set; what does it correspond to in the new set? I'm not seeing it at the moment... $\endgroup$
    – D.W. ♦
    Jan 30 '16 at 8:43
  • $\begingroup$ Right, this only works when $n-2$ is of the form $2^m-1$. But this doesn't sound like an insurmountable hurdle. $\endgroup$
    – Yuval Filmus
    Jan 30 '16 at 8:44
  • $\begingroup$ You have what we're interested in backwards. ​ ​ $\endgroup$
    – user12859
    Jan 30 '16 at 9:25
  • $\begingroup$ @RickyDemer I don't think so. $\endgroup$
    – Yuval Filmus
    Jan 30 '16 at 9:29
  • $\begingroup$ To be a parsimonious reduction from #-Subset-Sum to the OP's problem, we would need solutions in the new set to correspond to solutions in the old set. ​ Solutions in the new set are those summing to less than n-1, and solutions in the original set are those summing to exactly n-1. ​ You have things the other way around. ​ ​ ​ ​ $\endgroup$
    – user12859
    Jan 30 '16 at 9:40

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.