<p><strong>The problem you are asking about is #P-hard.</strong> Thanks to Stefan Mengel who gave me the arguments and gave me permission to post them here.</p>
<p>There are two points to the hardness proof (and two variants of the second point).</p>
<ul>
<li>Point 1: The problem, given a set <span class="math-container">$S$</span> of positive integers and a target <span class="math-container">$T$</span>, of counting how many subsets of <span class="math-container">$S$</span> sum up to <em>exactly</em> <span class="math-container">$T$</span>, is #P-hard. The rest of the answer clarifies this.</li>
<li>Point 2: The problem of summing to <em>exactly</em> <span class="math-container">$T$</span> reduces to your problem of summing to <em>at most</em> <span class="math-container">$T$</span>.</li>
</ul>
<h2>Proof of point 1</h2>
<p>The #P-hardness of the &quot;<em>exactly <span class="math-container">$T$</span></em>&quot; problem is claimed in <a href="http://arxiv.org/abs/1111.1224v1" rel="nofollow noreferrer">this article</a>, page 4, where they say it directly follows from the NP-hardness of SUBSET-SUM.</p>
<p>Looking into it, the hardness proof they adapt (Theorem 34.15 of <em><a href="https://en.wikipedia.org/wiki/Introduction_to_Algorithms" rel="nofollow noreferrer">Introduction to algorithms</a></em>) is a reduction from 3-CNF-SAT. Informally, you write numbers in base 10, and you code every literal as an element of the set <span class="math-container">$S$</span> with a <span class="math-container">$1$</span> in a variable-specific position, and a <span class="math-container">$1$</span> at the positions corresponding to clauses satisfied by the literal. The target <span class="math-container">$T$</span> has <span class="math-container">$1$</span> at all variable-specific positions, ensuring that subsets of <span class="math-container">$S$</span> summing to <span class="math-container">$T$</span> must take for each variable exactly one element of <span class="math-container">$S$</span> corresponding to a literal of that variable. Further, <span class="math-container">$S$</span> contains for every clause two &quot;slack elements&quot;, one with value 1 at the position corresponding to the clause, and one with value 2. The target <span class="math-container">$T$</span> asserts that the position of each clause contains 4. Hence, a subset of <span class="math-container">$S$</span> summing to <span class="math-container">$T$</span> must take at least one literal satisfying every clause (to get to 4), and then the choice of the slack elements (to complete to 4) is determined by the choice of variables.</p>
<p>So indeed I agree with them that this reduction is <a href="https://en.wikipedia.org/wiki/Parsimonious_reduction" rel="nofollow noreferrer">parsimonious</a>, i.e., there is a bijection between the satisfying assignments of the input 3-CNF-SAT instance and the subsets of <span class="math-container">$S$</span> summing to <span class="math-container">$T$</span>. As counting the satisfying elements is #P-hard, so is the &quot;<em>exactly <span class="math-container">$T$</span></em>&quot; problem. And so is your problem, as explained in the beginning of this post.</p>
<h2>Proof of point 2</h2>
<p>There are two variants to show this point. The first variant, point 2a below, is a simple argument but uses two oracle calls. The second variant, point 2b, shows the same thing but using only one oracle call.</p>
<h3>Proof of point 2a</h3>
<p>Given an instance <span class="math-container">$S$</span> and <span class="math-container">$T$</span>, to count how many subsets sum up to <em>exactly</em> <span class="math-container">$T$</span>, you can just use the oracle to your problem twice to find the number <span class="math-container">$N$</span> of subsets that sum up to <em>at most <span class="math-container">$T$</span></em>, and the number <span class="math-container">$N'$</span> of subsets that sum up to <em>at most <span class="math-container">$T-1$</span></em>. Then you can compute the value <span class="math-container">$N-N'$</span> which is the number of subsets summing to <em>exactly <span class="math-container">$T$</span></em>, the answer to the source problem.</p>
<h3>Proof of point 2b</h3>
<p>Here is an alternative proof of the reduction from the problem of point 1, which uses just one oracle call.</p>
<p>We want to know the number <span class="math-container">$K$</span> of subsets of <span class="math-container">$S$</span> that sum up to exactly <span class="math-container">$T$</span>. Let <span class="math-container">$N = |S|$</span> be the number of sets in <span class="math-container">$S$</span>. Let <span class="math-container">$S''$</span> be the set of <span class="math-container">$N+1$</span> singleton sets defined as <span class="math-container">$S'' = \{\{1\}, \ldots, \{N+1\}\}$</span>. Let <span class="math-container">$M = (N+1)(N+2)/2 + 1$</span> be a value greater than the sum of all integers of all sets in <span class="math-container">$S''$</span>: note that <span class="math-container">$M$</span> is polynomial. Let <span class="math-container">$MS$</span> be obtained from <span class="math-container">$S$</span> by multiplying all integers by <span class="math-container">$M$</span>, i.e., let <span class="math-container">$MU$</span> for a set of integers be <span class="math-container">$\{Mx \mid x \in U\}$</span>, and let <span class="math-container">$MS = \{MU \mid U \in S\}$</span>.</p>
<p>Now let <span class="math-container">$S' = MS \cup S''$</span>, which is a disjoint union because the sets of <span class="math-container">$S''$</span> contain integers less than <span class="math-container">$M$</span> and those of <span class="math-container">$MS$</span> contain positive integers no smaller than <span class="math-container">$M$</span>. Let <span class="math-container">$T' = MT$</span>. Call the oracle for OP's &quot;at least&quot; problem on <span class="math-container">$S'$</span> and <span class="math-container">$T'$</span>. Now, the answer <span class="math-container">$K'$</span> to the oracle call, giving the number of subsets of <span class="math-container">$S'$</span> summing to at most <span class="math-container">$T'$</span>, is the sum of two types of solutions:</p>
<ul>
<li>Type 1: take sets of <span class="math-container">$MS$</span> summing to <em>exactly</em> <span class="math-container">$MT$</span>, and take no set of <span class="math-container">$S'$</span>: as everything has been multiplied by <span class="math-container">$M$</span> we see that the number of solutions of type 1 is exactly the value <span class="math-container">$K$</span> that we wanted to compute.</li>
<li>Type 2: take sets of <span class="math-container">$MS$</span> summing to strictly less than <span class="math-container">$MT$</span>, and independently take any combination of sets of <span class="math-container">$S''$</span> (they all sum to less than <span class="math-container">$M$</span>), i.e., <span class="math-container">$2^{N+1}$</span> combinations: call <span class="math-container">$K'$</span> this number of solutions of type 2, which is a multiple of <span class="math-container">$2^{N+1}$</span>.</li>
</ul>
<p>The oracle call has returned <span class="math-container">$K'' = K + K'$</span>. Now, we know that <span class="math-container">$K'$</span> is a multiple of <span class="math-container">$2^{N+1}$</span>, and know that <span class="math-container">$K \leq 2^N$</span>, so we have <span class="math-container">$K = K'' \text{ mod } 2^{N+1}$</span>. This explains how to recover the value <span class="math-container">$K$</span> that we wanted to compute from the oracle answer <span class="math-container">$K'$</span>.</p>
<p>The point of this reduction is that it uses only one oracle call (but post-processes the answer).</p>

CC BY-SA 4.0
2024-01-18T18:49:01.233Z
Thanks a lot for your insightful answer and article! That's what I tried too, the problem I see with that approach is that the reduction disregards the number of subsets that have a sum less than T. In fact, the decision problem: does this set of positive integers have a subset with a sum of at most T is in P(the empty set has a sum of zero so if T < 0 answer False, otherwise, True). Notice that if a parsimonious reduction exists between any NP-Hard problem and the aforementioned problem, then P = NP since the counting version has an FPTAS( see [link](https://arxiv.org/abs/1802.05791) ).
Daniel García
CC BY-SA 4.0
2024-01-19T08:25:52.393Z
@DanielGarcía: oh, I see, sorry that I misread your question. Indeed, that's a problem -- the number of subsets with sum at most T in the answer is the number of Boolean assignments but weighted in a strange way (depending on how many true literals there are in the various clauses). I'd have to think more, sorry...
Antoine Amarilli 'a3nm'
CC BY-SA 4.0
2024-01-19T21:56:22.363Z
No worries, like I said it was the most natural way to go. I have a lower bound for the number of subsets with a sum over T following the reduction, it's 2^(n-2) (n is the number of integers in the set). That's because summing the two largest elements from the set gives you a sum of 200... which is greater than the target sum, you then can use any combination of the remaining elements to get a greater sum. However, it's just a lower bound and doesn't help much for our problem, since it over-counts the number of subsets with a sum less than T.
Daniel García
CC BY-SA 4.0
2024-03-07T15:38:57.243Z
@DanielGarcía: my collaborator Stefan pointed out there is an immediate reduction from "exactly $T$" to "at most $T$", so your problem is hard as well. I updated my answer to reflect it. I hope this helps!
Antoine Amarilli 'a3nm'
CC BY-SA 4.0
2024-03-07T17:43:58.723Z
Thanks a lot for your insightful and simple answer!
Daniel García
CC BY-SA 4.0
2024-03-11T12:24:52.370Z
That's not a many-one counting reduction though, so this only proves #P hardness under Turing reductions (in fact this exact reduction is why I asked OP if he insisted on many-one counting reductions)
Tassle
CC BY-SA 4.0
2024-03-14T00:03:34.373Z
@a3nm: Tassle has a good point, my apologies for not modifying the original post. Do you mind modifying your original answer to reflect the fact that the oracle is used once?
Daniel García
CC BY-SA 4.0
2024-03-14T09:28:32.717Z
@DanielGarcía: Sure, I have moved my comments to the answer itself (and deleted the comments)
Antoine Amarilli 'a3nm'
CC BY-SA 4.0
2024-01-18T10:25:23.413Z
2024-03-14T09:27:46.347Z
2024-03-14T09:27:46.347Z
Antoine Amarilli 'a3nm'
<p>Just to add to the answer of a3nm:</p>
<p>The problem is also known as #Knapsack, which is the counting version of the knapsack problem. The constraint that the sum of the selected numbers needs to be smaller than <span class="math-container">$T$</span> is a knapsack constraint.</p>
<p><s> This problem is discussed in &quot;Computers and Intractability: A Guide to the Theory of NP-completeness&quot; by Garey and Johnson. </s></p>
<p>This term is used, for instances, in <a href="https://ieeexplore.ieee.org/abstract/document/6108252" rel="nofollow noreferrer">this</a> article of Gopalan et al. (2011).</p>
<p>The problem is also discussed in <a href="https://www.cambridge.org/core/journals/combinatorics-probability-and-computing/article/abs/mildly-exponential-time-algorithm-for-approximating-the-number-of-solutions-to-a-multidimensional-knapsack-problem/A2800AB5DECA30E73112853AD562AD6B" rel="nofollow noreferrer">this</a> article by Dyer et al. (1993) however, there the term &quot;#Knapsack&quot; is not used explicitly.</p>
<p>Unfortunately I am not aware of the first article that used the term &quot;#Knapsack&quot; nor the original source that proved that this problem is #P-complete.</p>

CC BY-SA 4.0
2024-03-18T08:56:59.440Z
Is it called #Knapsack in Garey and Johnson? To me, it seems to be the Kth Largest Subset Problem defined in Chapter 5.1.
Christian Komusiewicz
CC BY-SA 4.0
2024-03-18T08:57:24.427Z
Your answer could be improved with additional supporting information. Please [edit] to add further details, such as citations or documentation, so that others can confirm that your answer is correct. You can find more information on how to write good answers [in the help center](/help/how-to-answer).
Community
CC BY-SA 4.0
2024-03-12T12:45:33.703Z
2024-03-19T15:51:09.520Z
2024-03-19T15:51:09.520Z
badboul
<p>Consider the given problem: you have a set S of positive integers, and you want to find how many subsets have a sum of at most T. I highly suspect that the problem is hard since a polynomial time algorithm for the problem would give a polynomial time algorithm for #Subset-Sum. I have tried reducing from #Subset-Sum, but unsuccessfully. The main difficulty I face is linking the number of subsets and the maximum sum such that the resulting number of subsets can be expressed by an algebraic expression following the reduction. Is it possible to prove #P-hardness under many-one counting reductions?</p>

CC BY-SA 4.0
2024-01-14T18:44:18.467Z
Can you define exactly what you mean by "#Subset-Sum"? There are a few different variants of the Subset-Sum problem, which lead to different counting versions. Also, what type of reduction are you looking for (Turing, Many-one, deterministic, randomized,...)? For Turing reductions, I think it is easy, but the way you ask the question makes me think you are looking for a many-one counting reduction.
Tassle
CC BY-SA 4.0
2024-01-16T23:38:31.283Z
@Tassle Sorry for the lack of detail. I define #Subset-Sum as counting the number of subsets of a set S that have a sum of exactly T and I was looking for a many-one reduction (given a hypothetical algorithm and a reduced instance, counting solutions in the reduced instance would also allow counting solutions in the original instance in one algorithm call). I reduced from 3-SAT to Subset-Sum parsimoniously to put some restrictions on the set and the sum T, however, I think that it's a dead end because I wasn't able to find an expression for the number of subsets with a sum less than T.
Daniel García
<co.combinatorics><counting-complexity><reductions>
Proving #P-hardness for the number of subsets of a set of positive integers with a sum of at most T?
Daniel García
# Proving #P-hardness for the number of subsets of a set of positive integers with a sum of at most T?

(Asked by: username_0 on 2024-01-11)

Consider the given problem: you have a set S of positive integers, and you want to find how many subsets have a sum of at most T. I highly suspect that the problem is hard since a polynomial time algorithm for the problem would give a polynomial time algorithm for #Subset-Sum. I have tried reducing from #Subset-Sum, but unsuccessfully. The main difficulty I face is linking the number of subsets and the maximum sum such that the resulting number of subsets can be expressed by an algebraic expression following the reduction. Is it possible to prove #P-hardness under many-one counting reductions?

**Tags:** co.combinatorics, counting-complexity, reductions

> **Comments:**
> **username_1**: Can you define exactly what you mean by "#Subset-Sum"? There are a few different variants of the Subset-Sum problem, which lead to different counting versions. Also, what type of reduction are you looking for (Turing, Many-one, deterministic, randomized,...)? For Turing reductions, I think it is easy, but the way you ask the question makes me think you are looking for a many-one counting reduction.  
> **username_0**: @username_1 Sorry for the lack of detail. I define #Subset-Sum as counting the number of subsets of a set S that have a sum of exactly T and I was looking for a many-one reduction (given a hypothetical algorithm and a reduced instance, counting solutions in the reduced instance would also allow counting solutions in the original instance in one algorithm call). I reduced from 3-SAT to Subset-Sum parsimoniously to put some restrictions on the set and the sum T, however, I think that it's a dead end because I wasn't able to find an expression for the number of subsets with a sum less than T.  

---

## 2 answers

### Answer by username_2 on 2024-01-18. Score: 3 | Accepted answer

**The problem you are asking about is #P-hard.** Thanks to Stefan Mengel who gave me the arguments and gave me permission to post them here.

There are two points to the hardness proof (and two variants of the second point).

* Point 1: The problem, given a set $S$ of positive integers and a target $T$, of counting how many subsets of $S$ sum up to *exactly* $T$, is #P-hard. The rest of the answer clarifies this.
* Point 2: The problem of summing to *exactly* $T$ reduces to your problem of summing to *at most* $T$.

## Proof of point 1

The #P-hardness of the "*exactly $T$*" problem is claimed in [this article](http://arxiv.org/abs/1111.1224v1), page 4, where they say it directly follows from the NP-hardness of SUBSET-SUM.

Looking into it, the hardness proof they adapt (Theorem 34.15 of *[Introduction to algorithms](https://en.wikipedia.org/wiki/Introduction_to_Algorithms)*) is a reduction from 3-CNF-SAT. Informally, you write numbers in base 10, and you code every literal as an element of the set $S$ with a $1$ in a variable-specific position, and a $1$ at the positions corresponding to clauses satisfied by the literal. The target $T$ has $1$ at all variable-specific positions, ensuring that subsets of $S$ summing to $T$ must take for each variable exactly one element of $S$ corresponding to a literal of that variable. Further, $S$ contains for every clause two "slack elements", one with value 1 at the position corresponding to the clause, and one with value 2. The target $T$ asserts that the position of each clause contains 4. Hence, a subset of $S$ summing to $T$ must take at least one literal satisfying every clause (to get to 4), and then the choice of the slack elements (to complete to 4) is determined by the choice of variables.

So indeed I agree with them that this reduction is [parsimonious](https://en.wikipedia.org/wiki/Parsimonious_reduction), i.e., there is a bijection between the satisfying assignments of the input 3-CNF-SAT instance and the subsets of $S$ summing to $T$. As counting the satisfying elements is #P-hard, so is the "*exactly $T$*" problem. And so is your problem, as explained in the beginning of this post.

## Proof of point 2

There are two variants to show this point. The first variant, point 2a below, is a simple argument but uses two oracle calls. The second variant, point 2b, shows the same thing but using only one oracle call.

### Proof of point 2a

Given an instance $S$ and $T$, to count how many subsets sum up to *exactly* $T$, you can just use the oracle to your problem twice to find the number $N$ of subsets that sum up to *at most $T$*, and the number $N'$ of subsets that sum up to *at most $T-1$*. Then you can compute the value $N-N'$ which is the number of subsets summing to *exactly $T$*, the answer to the source problem.

### Proof of point 2b

Here is an alternative proof of the reduction from the problem of point 1, which uses just one oracle call.

We want to know the number $K$ of subsets of $S$ that sum up to exactly $T$. Let $N = |S|$ be the number of sets in $S$. Let $S''$ be the set of $N+1$ singleton sets defined as $S'' = \{\{1\}, \ldots, \{N+1\}\}$. Let $M = (N+1)(N+2)/2 + 1$ be a value greater than the sum of all integers of all sets in $S''$: note that $M$ is polynomial. Let $MS$ be obtained from $S$ by multiplying all integers by $M$, i.e., let $MU$ for a set of integers be $\{Mx \mid x \in U\}$, and let $MS = \{MU \mid U \in S\}$.

Now let $S' = MS \cup S''$, which is a disjoint union because the sets of $S''$ contain integers less than $M$ and those of $MS$ contain positive integers no smaller than $M$. Let $T' = MT$. Call the oracle for OP's "at least" problem on $S'$ and $T'$. Now, the answer $K'$ to the oracle call, giving the number of subsets of $S'$ summing to at most $T'$, is the sum of two types of solutions:

* Type 1: take sets of $MS$ summing to *exactly* $MT$, and take no set of $S'$: as everything has been multiplied by $M$ we see that the number of solutions of type 1 is exactly the value $K$ that we wanted to compute.
* Type 2: take sets of $MS$ summing to strictly less than $MT$, and independently take any combination of sets of $S''$ (they all sum to less than $M$), i.e., $2^{N+1}$ combinations: call $K'$ this number of solutions of type 2, which is a multiple of $2^{N+1}$.

The oracle call has returned $K'' = K + K'$. Now, we know that $K'$ is a multiple of $2^{N+1}$, and know that $K \leq 2^N$, so we have $K = K'' \text{ mod } 2^{N+1}$. This explains how to recover the value $K$ that we wanted to compute from the oracle answer $K'$.

The point of this reduction is that it uses only one oracle call (but post-processes the answer).

> **Comments:**
> **username_0**: Thanks a lot for your insightful answer and article! That's what I tried too, the problem I see with that approach is that the reduction disregards the number of subsets that have a sum less than T. In fact, the decision problem: does this set of positive integers have a subset with a sum of at most T is in P(the empty set has a sum of zero so if T < 0 answer False, otherwise, True). Notice that if a parsimonious reduction exists between any NP-Hard problem and the aforementioned problem, then P = NP since the counting version has an FPTAS( see [link](https://arxiv.org/abs/1802.05791) ).  
> **username_2**: @DanielGarcía: oh, I see, sorry that I misread your question. Indeed, that's a problem -- the number of subsets with sum at most T in the answer is the number of Boolean assignments but weighted in a strange way (depending on how many true literals there are in the various clauses). I'd have to think more, sorry...  
> **username_0**: No worries, like I said it was the most natural way to go. I have a lower bound for the number of subsets with a sum over T following the reduction, it's 2^(n-2) (n is the number of integers in the set). That's because summing the two largest elements from the set gives you a sum of 200... which is greater than the target sum, you then can use any combination of the remaining elements to get a greater sum. However, it's just a lower bound and doesn't help much for our problem, since it over-counts the number of subsets with a sum less than T.  
> **username_2**: @DanielGarcía: my collaborator Stefan pointed out there is an immediate reduction from "exactly $T$" to "at most $T$", so your problem is hard as well. I updated my answer to reflect it. I hope this helps!  
> **username_0**: Thanks a lot for your insightful and simple answer!  
> **username_1**: That's not a many-one counting reduction though, so this only proves #P hardness under Turing reductions (in fact this exact reduction is why I asked OP if he insisted on many-one counting reductions)  
> **username_0**: @a3nm: username_1 has a good point, my apologies for not modifying the original post. Do you mind modifying your original answer to reflect the fact that the oracle is used once?  
> **username_2**: @DanielGarcía: Sure, I have moved my comments to the answer itself (and deleted the comments)  

---

### Answer by username_3 on 2024-03-12. Score: 1

Just to add to the answer of a3nm:

The problem is also known as #Knapsack, which is the counting version of the knapsack problem. The constraint that the sum of the selected numbers needs to be smaller than $T$ is a knapsack constraint.

~~This problem is discussed in "Computers and Intractability: A Guide to the Theory of NP-completeness" by Garey and Johnson.~~

This term is used, for instances, in [this](https://ieeexplore.ieee.org/abstract/document/6108252) article of Gopalan et al. (2011).

The problem is also discussed in [this](https://www.cambridge.org/core/journals/combinatorics-probability-and-computing/article/abs/mildly-exponential-time-algorithm-for-approximating-the-number-of-solutions-to-a-multidimensional-knapsack-problem/A2800AB5DECA30E73112853AD562AD6B) article by Dyer et al. (1993) however, there the term "#Knapsack" is not used explicitly.

Unfortunately I am not aware of the first article that used the term "#Knapsack" nor the original source that proved that this problem is #P-complete.

> **Comments:**
> **username_4**: Is it called #Knapsack in Garey and Johnson? To me, it seems to be the Kth Largest Subset Problem defined in Chapter 5.1.  
> **username_5**: Your answer could be improved with additional supporting information. Please [edit] to add further details, such as citations or documentation, so that others can confirm that your answer is correct. You can find more information on how to write good answers [in the help center](/help/how-to-answer).  

---

