# Subset sum with many targets

Take a set $S = \{a_1, a_2, ..., a_n\}$ of integers $a_i$ and a set $G = \{b_1, b_2, ..., b_m\}$ of integers $b_j$.

If we ask the question, is there a subset $C \subseteq S$ such that the sum $(\sum_{a_i \in C} a_i) \in G$, and $m = 1$ this is the traditional subset sum problem. We add an additional restriction (so that this is a promise problem) that all $b_j \in G$ must be between the minimum sum and the maximum sum of subsets of $S$.

I have three questions regarding the case where $m \gt 1$.

1.) Is there a known name for this problem and has it been studied?

2.) Are there threshold results for this problem, or can threshold results from k-SAT problems be reduced to this problem?

3.) Are there known or obvious instances where this problem is trivial? Or in general does it remain NP-Complete?

Edit: Threshold results - for a uniformally random selected set $S$ and $G$ of given sizes whose integer members are limited in size (under the usual binary encoding) of $b$ bits, and for a fixed ratio $k = |G|/|S|$, is there a $k$ for which the multiple target subset sum problem becomes almost certainly satisfiable or unsatisfiable (in the manner of 3-SAT)?

• For 3) It is still NPC: if $m$ is a parameter, then it is a generalization of SUBSET SUM. If $m$ is fixed, then given an instance of SUBSET SUM, simply multiply every $a_i$ and the target sum $B$ by $2^k$ s.t. $2^k > m(m+1)/2$ and set $m$ target integers $b_1=B, b_2 = a_1+1, b_3=a_1+2,...,b_m = a_1+{m-1}$. In both cases it also remains solvable in pseudo-polynomial time. – Marzio De Biasi Dec 24 '14 at 8:20
• @MarzioDeBiasi Nice reduction! – Jason Knight Dec 24 '14 at 16:16
• What does "threshold results" mean in this context? Please clarify by editing the question. – Tsuyoshi Ito Dec 25 '14 at 14:42
• I cannot understand your edit about "threshold results." Which set are S and G chosen from? In addition, intuitively, increasing |S| makes the instance more likely to be satisfiable, and so does increasing |G|, so fixing the ratio |G|/|S| does not seem to make sense. – Tsuyoshi Ito Dec 30 '14 at 7:27
• @Tsuyoshilto These sets are chosen uniformally from all sets of a certain size whose integer members are within a certain bit size limit $b$ (under the usual binary encoding). I would certainly welcome a characterization of threshold that doesn't take a ratio if it captured the asymptotic likelihood of a given instance (taken uniformally) to be varifiable. Thanks for the questions! – Jason Knight Dec 30 '14 at 17:33

## 1 Answer

For what regards point 3: the problem remains NP-complete:

• if $m$ is a parameter, then it is simply a generalization of SUBSET SUM;

• if $m$ is fixed, then given an instance of SUBSET SUM, simply multiply every $a_i$ and the target sum $B$ by $p = 2^k$ s.t. $2^k>m(m+1)/2$ and set $m$ target integers in this way:

$G = \{ b_1=B,b_2=a_1+1,b_3=a_1+2,...,b_m=a_1+(m−1)\}$.

In both cases the problem remains solvable in pseudo-polynomial time.

For what regards point 2) you can find some information related to the density analysis for the ("simpler") SUBSET-SUM problem (it is usually defined in terms of $n/m$ where $n$ is the number of elements of the input set and $m$ is its maximum); e.g.: O'Neil, Thomas E. "On Clustering in the Subset Sum Problem." Proceedings of the 44th Midwest Instruction and Computing Symposium (Duluth, MN, 2011).