<p>For what regards point 3:  the problem remains NP-complete: </p>

<ul>
<li><p>if $m$ is a parameter, then it is simply a generalization of SUBSET SUM;</p></li>
<li><p>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&gt;m(m+1)/2$ and set $m$ target integers in this way: </p></li>
</ul>

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

<p>In both cases the problem remains solvable in pseudo-polynomial time.</p>

<p>For what regards point 2) you can find some information related to the <em>density</em> 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).</p>

CC BY-SA 3.0
2015-01-02T08:01:32.933Z
Is problem here similar http://cstheory.stackexchange.com/questions/28015/weighted-exponential-range-subset-sum?
Turbo
CC BY-SA 3.0
2014-12-27T19:03:13.563Z
2014-12-27T19:03:13.563Z
Marzio De Biasi
<p>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$.</p>

<p>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$.</p>

<p>I have three questions regarding the case where $m \gt 1$.</p>

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

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

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

<p><strong>Edit</strong>: 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)?</p>

CC BY-SA 3.0
2014-12-24T08:20:39.240Z
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
CC BY-SA 3.0
2014-12-24T16:16:00.330Z
@MarzioDeBiasi Nice reduction!
Jason Knight
CC BY-SA 3.0
2014-12-25T14:42:12.973Z
What does "threshold results" mean in this context?  Please clarify by editing the question.
Tsuyoshi Ito
CC BY-SA 3.0
2014-12-30T07:27:20.673Z
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
CC BY-SA 3.0
2014-12-30T17:33:52.417Z
@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
CC BY-SA 3.0
2014-12-31T07:38:08.490Z
Please integrate your clarifications into the question so that other people do not have to read comments to understand the question.
Tsuyoshi Ito
<subset-sum>
Subset sum with many targets
Jason Knight
# Subset sum with many targets

(Asked by: username_0 on 2014-12-24)

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)?

**Tags:** subset-sum
> **Comments:**
> **username_1**: 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.  
> **username_0**: @MarzioDeBiasi Nice reduction!  
> **username_2**: What does "threshold results" mean in this context?  Please clarify by editing the question.  
> **username_2**: 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.  
> **username_0**: @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!  
> **username_2**: Please integrate your clarifications into the question so that other people do not have to read comments to understand the question.  

---

## 1 answers

### Answer by username_1 on 2014-12-27. Score: 3

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

> **Comments:**
> **username_3**: Is problem here similar http://cstheory.stackexchange.com/questions/28015/weighted-exponential-range-subset-sum?  

---

