7
$\begingroup$

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?

$\endgroup$
2
  • 1
    $\begingroup$ 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. $\endgroup$
    – Tassle
    Jan 14 at 18:44
  • $\begingroup$ @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. $\endgroup$ Jan 16 at 23:38

2 Answers 2

3
$\begingroup$

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, 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) 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, 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).

$\endgroup$
8
  • $\begingroup$ 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 ). $\endgroup$ Jan 18 at 18:49
  • $\begingroup$ @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... $\endgroup$
    – a3nm
    Jan 19 at 8:25
  • $\begingroup$ 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. $\endgroup$ Jan 19 at 21:56
  • $\begingroup$ @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! $\endgroup$
    – a3nm
    Mar 7 at 15:38
  • 1
    $\begingroup$ 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) $\endgroup$
    – Tassle
    Mar 11 at 12:24
1
$\begingroup$

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 article of Gopalan et al. (2011).

The problem is also discussed in this 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.

$\endgroup$
2
  • $\begingroup$ Is it called #Knapsack in Garey and Johnson? To me, it seems to be the Kth Largest Subset Problem defined in Chapter 5.1. $\endgroup$ Mar 18 at 8:56
  • $\begingroup$ 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. $\endgroup$
    – Community Bot
    Mar 18 at 8:57

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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