Suppose I have a sequence, where for each element I can choose one out of two numbers. I would like to find a compact formula to write all the possible sums of all the possible sequences.

For example, suppose I have $\langle(1,2), (3,4) \rangle$

The possible sequences are $\langle 1, 3 \rangle$, $\langle 1, 4 \rangle$, $\langle 2, 3\rangle$, $\langle 2, 4\rangle$ and therefore all the possible sums are $4, 5, 5, 6$ respectively.

  • 3
    $\begingroup$ Do we have any additional structure on the types of numbers you are selecting from? I imagine if there was none at all, then not really all that much can be said (of course I might be mistaken, math is full of surprises!) $\endgroup$ – frogeyedpeas Dec 19 '15 at 8:00
  • $\begingroup$ What do you mean by "compact formula"? $\endgroup$ – Kyle Jones Dec 23 '15 at 0:07

It seems that the following holds. Assume that the compact formula is so good that it is effectively computable (which, in general, probably, is not true, for instance, for a formula $\tan 2^{2^n}$ (?)). Next, to be independent on a definition of a computation algorithm, we assume the Church-Turing thesis. Then your question has a negative answer (even if we consider only non-negative integers) because it asks about an NP-complete problem. Indeed, from one side, the sum listing problem is in NP, because it can be solved by $2^n$ independent automata in linear time. From the other side, given a set $A=\{a_1,\dots, a_n\}$ of natural numbers and a natural number $b$, to decide whether there exists a subset of $A$ whose sum is $b$ is a well-known decision problem; the subset sum problem, which is NP-hard. So if we consider the pairs $\langle (a_1,0),\dots, (a_n,0)\rangle$, the problem to decide whether $b$ is the sum of a possible sequence is NP-hard, too. Conversely, to decide whether $b$ is the sum of a possible sequence of the pairs $\langle (a_1,b_1),\dots, (a_n,b_n)\rangle$, it suffices to decide whether $b-(a_1+\cdots+a_n)$ is the sum of a possible sequence of a submultiset of a multiset $\{b_1-a_1,\dots, b_n-a_n\}$.

Acknowledgement. Author thanks to Prof. Dr. Alexander Wolff for his valuable remarks and corrections.


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.