SUBSET-SUM, upper bound on number of solutions

As you probably know, the SUBSET-SUM problem is defined as determining if a subset of a set of whole numbers sum to a specified whole number. (there is another definition of subset-sum, where a group of integers sum to zero, but let's use this definition for now)

For example ((1,2,4,5),6) is true because (2,4) sums to 6. We say that (2,4) is a "solution"

Furthermore, ((1,5,10),7) is false because nothing in the arguments sum to 7

My question is, given a set of argument numbers for SUBSET-SUM is there a polynomial upp开发者_运维百科er bound on the number of possible solutions. In the first example there was (2,4) and (1,5).

We know that since SUBSET-SUM is NP-complete deciding in polynomail time probably is impossible. However my question is not related to the decision time, I'm asking strictly about the size of the list of solutions.

Obviously the size of the power set of the argument numbers can be an upper bound on solution list size, however this has exponential growth. My intuition is that there should be a polynomial bound, but I cannot prove this.

nb I know this sounds like a homework question, but please trust me it isn't. I am trying to teach myself certain aspects of CS theory and this is where my thoughts have taken me.

---

No; take numbers:

(1, 2, 1+2, 4, 8, 4+8, 16, 32, 16+32, ..., 2²ⁿ, 2²ⁿ⁺¹, 2²ⁿ+2²ⁿ⁺¹)

and ask about forming the sum 1 + 2 + 4 + ... + 2²ⁿ + 2²ⁿ⁺¹. (For example: with n = 3 take the set (1,2,3,4,8,12,16,32,48) and ask about the subsets summing to 63.)

You can form 1+2 either using 1 and 2 or using 1+2.

You can form 4+8 either using 4 and 8 or using 4+8.

....

You can form 2²ⁿ + 2²ⁿ⁺¹ either using 2²ⁿ and 2²ⁿ⁺¹ or 2²ⁿ+2²ⁿ⁺¹.

The choices are independent, so there are at least 3ⁿ=3^m/3, where m is the size of your set. I bet this can be sharply strengthened, but this proves there's no polynomial bound.

---

Sperner's Theorem provides a nice (albeit non-polynomial) upper bound, at least in the case when the numbers in the set are strictly greater than zero (as seems to be the case in your problem).

The family of all subsets with a given sum form a Sperner family, which is a collection of subsets where no subset in the family is itself a subset of any of the other subsets in the family. This is where the assumption that the elements are strictly greater than zero is used. Sperner's theorem states that the maximum size of such a Sperner family is given by the binomial coefficient n Choose floor(n/2).

If you drop the assumption that the n numbers are distinct, it is easy to see that this upper bound can't be improved (just take all numbers = 1 and let the target sum be floor(n/2)). I don't know if it can be improved under the assumption that the numbers are distinct.