2
$\begingroup$

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

Improve this question
$\endgroup$
6
  • 3
    $\begingroup$ 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. $\endgroup$
    – Marzio De Biasi
    Dec 24, 2014 at 8:20
  • $\begingroup$ @MarzioDeBiasi Nice reduction! $\endgroup$
    – Jason Knight
    Dec 24, 2014 at 16:16
  • $\begingroup$ What does "threshold results" mean in this context? Please clarify by editing the question. $\endgroup$
    – Tsuyoshi Ito
    Dec 25, 2014 at 14:42
  • $\begingroup$ 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. $\endgroup$
    – Tsuyoshi Ito
    Dec 30, 2014 at 7:27
  • $\begingroup$ @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! $\endgroup$
    – Jason Knight
    Dec 30, 2014 at 17:33

1 Answer 1

Reset to default
3
$\begingroup$

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

Improve this answer
$\endgroup$
1

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.