# More Subset Sums

Shit, I made the mistake of thinking about them, and now I'm back on it.

We'll try the opposite tack this time, though: proving that it's impossible to solve in polynomial time.

Stream of consciousness begins:

- Consider the unconstrained case where %S% is the set of integers provided, of finite but arbitrarily large length.
- Likewise, let each element be a randomly chosen finite integer from %\mathbb{Z}%.
- That opens shit up. If we content ourselves for the moment with only considering large sets of large numbers, we see that (well, I'm assuming that)...
- All possible subsets %S' \subseteq S% will sum to between %1% and %2^|S| - 1% unique values, inclusive.
- For example, %S = {0, 0, 0}% can only yield %0%, and %S = {1, 4, 10}% could yield %{1, 4, 5, 10, 11, 14, 15}%.

- Granted, this doesn't narrow things down much. But recall, we're looking at the big case. The question becomes:
- Given %S%, and from that, %|S|% and %max(S) - min(S)%, how can we approximate our expected number of unique sums?

- I don't know. But I
*do*know that the further the range of %S% outstrips the length of %S%, the number of unique sums will asymptotically approach %2^|S|%.- And that seems valuable, so long as we assume that our integers are randomly, normally distributed.

- All possible subsets %S' \subseteq S% will sum to between %1% and %2^|S| - 1% unique values, inclusive.

For example. Let us select a more well-defined %S% of length %10%, and declare that its elements are selected at random from the range %\pm 10^100%. It is then essentially a mathematical certainty that the set of all possible sums will be a set of length %~= 2^|S| - 1 \approx 1023%. Clearly still not able to make a statistically significant dent in our range, and since the numbers were by definition chosen randomly to begin with, their unique sums should also be random. [*N.B. This raises the side-investigation for later of how many times one would have to repeat this process, iteratively generating sets from sums of power sets, beginning with random input, before everything levels out...*]

I don't know if that necessarily follows, but it feels right, especially when dealing with absurdly large numbers. Moreover, if it doesn't follow, that fact likely has implications at least as interesting as anything we're heading toward now.

But let us suppose you can safely assume that the set of all subset sums here is itself truly random (or close enough so as not to matter..., well, I get the sense there's something there.

Ah. Yeah, I think I see it. If we were allowed to cheat and declare that as truly and necessarily random, we could go on to show that the problem becomes indistinguishable from being handed a sequence of random integers and being asked if any of them are a certain value, and doing it *more* efficiently than %O(N)%, which I take as self-evident to be impossible. Note that even with %O(N)% efficiency there, it back-equates to %O(2^N)% in our actual case. I think.

Okay, my reasoning must be flawed, because writing that big-O reminded me that the current best algorithm solves the general case in %O(2^(N//2))% time; thus, either I read that wrong on Wikipedia, or the 40-year-old well-established paper establishing that result is wrong, my understanding of the potential assumptions of the problem are wrong, or my logic chain in the past few paragraphs was wrong. Let's see...

Yep, never mind. I was wildly off about this. The last entry, too.