4
$\begingroup$

I am considering a problem of the following: Given a set $X$ of integers and another integer B, are there two subsets of $X$, say $X_1$ and $X_2$, such that $X_1-X_2=B$ ? (Here, $X_i$ also denotes the sum of integers in the set $X_i$)

I wonder whether this problem is solvable in polytime or NP-complete? Thanks.

|cite|improve this question
$\endgroup$
  • 3
    $\begingroup$ en.wikipedia.org/wiki/Partition_problem $\endgroup$ – R B Nov 25 '14 at 13:10
  • 2
    $\begingroup$ A reduction from the partition problem isn't all that straightforward, given that (in the current formulation) X1 and X2 do not need to be a partition of X. They could just be the empty set, so you don't get away with setting B=0. It is still NP-complete though, you just need to employ a little trickery in the reduction from partition. $\endgroup$ – Tom van der Zanden Nov 25 '14 at 13:47
  • 4
    $\begingroup$ Partition is the right choice if $X_1 \cup X_2 = X; X_1 \cap X_2 = \emptyset$; if you need a relaxed condition: $X_1,X_2 \neq \emptyset$, $X_1, X_2 \subseteq X; X_1 \cap X_2 = \emptyset$ then pick $B = 0$ and you get the Equal-subset-sum problem which is still NPC. $\endgroup$ – Marzio De Biasi Nov 25 '14 at 13:59
  • $\begingroup$ @MarzioDeBiasi, comment --> answer? $\endgroup$ – usul Nov 25 '14 at 18:28
  • $\begingroup$ @Tom van der Zanden: Could you elaborate on the “little trickery”? It is believable such modification can be done, but I cannot see how. $\endgroup$ – Tsuyoshi Ito Nov 25 '14 at 19:59
7
$\begingroup$

As said by RB in the comment, if $X_1 \cup X_2 = X; X_1 \cap X_2 = \emptyset$, then setting $B=0$ makes your problem equivalent to PARTITION. But even with the relaxed conditions: $X_1,X_2 \neq \emptyset, X_1, X_2 \subseteq X; X_1 \cap X_2 = \emptyset$ (i.e. $X_1,X_2$ not necessarily form a partition of $X$) the problem is still NPC: set $B = 0$ and it becomes equivalent to the EQUAL-SUBSET-SUM problem.

I don't bear papers behind paywalls :-), so this is a quick sketch of an alternative simple reduction from SUBSET-SUM:

Given non-negative integers $A = \{ a_1,a_2,...,a_n\}$ and a target sum $S$, let $k = \lceil \log \sum a_i \rceil$.

  • For $i = 1,...,n$, set $x_i = 2^{k+3i} + a_i$,
  • add $n$ new integers $x'_i = 2^{k+3i}$,
  • add two dum integers $d_1 = d_2 = 2^{k+3(n+1)}$ that are used only to make $X_2$ nonempty
  • and finally set as target sum (for your problem) $B = S + \sum_{i=1}^n 2^{k+3i}$

The following figure should make things clearer:

enter image description here
(empty cells represent zeros)

If there is a subset $A'$ that sums to $S$ in the original problem, then $X_1 = \{ x_i \mid a_i \in A' \} \cup \{ x'_i \mid a_i \notin A'\} \cup \{d_1\}$, $X_2 = \{d_2\}$ are such that $X_1 - X_2 = B$.

In the opposite direction, suppose that $X_1 - X_2 = B$, then it is easy to prove that if you include one of the $x_i$ (or $x'_i$) in $X_2$, i.e. you subtract them, you'll not be able to "totalize" the $2^{k+3i}$ component of the target sum $B$ anymore. So none of the $x_i$ can be included in $X_2$, and $\sum_{\{ i \mid x_i \in X_1\}} a_i = S$

|cite|improve this answer
$\endgroup$
  • $\begingroup$ Is there a reason why we're specifically adding $2^{k + 3i}$ in $x_i$ and $x'_i$ above? As in, shouldn't it work if I just add say $2^i$? Or in other words, I would like to know the motivation behind adding $2^{k + 3i}$ in particular. Also, I have a doubt regarding the figure. For instance, consider $x_n$. Shouldn't the 1 be in the $(k + 3n)$ bit position and not in the kth position? And similarly for $x_1$, shouldn't it be 1 in the $k$th position and not the $(k+3n)$ position? $\endgroup$ – anon. computer scientist Mar 10 '15 at 17:20
  • $\begingroup$ @anon.computerscientist: very informally, $k$ is used to avoid interference between the lowest $a_i$ and the new added high bits. The reason for $3i$ is to make enough "space" between the bits to avoid unwanted interferences. For example if you sum $x_1, x'_1, B$, the resulting sum has bit $2^{k+5}$ set, but it is not enough to interfere with the $2^{k+6}$ of $x_2$. I made the proof quickly so it can surely be optimized; for instance it is enough to set $x_i = 2^{k+3(i-1)}$ for $i = 1..n$ ($x_1 = 2^k+a_1$, $x_2 = 2^{k+3}+a_2$, $x_3 = 2^{k+6}+a_3$,...). Let me know if you need more details. $\endgroup$ – Marzio De Biasi Mar 10 '15 at 19:04
  • $\begingroup$ I'm sorry if this's bothering. But I'm not able to exactly understand why we need to be bothered about the interferences. I mean, given the set A' which sums to S, we can anyway identify the corresponding $x_i$'s & $x'_i$'s which need to be added to the set $X_1$. And similarly, in the converse, any interference doesn't seem to make the argument void. So the way I see it, the only reason we need the dependence on $i$ in $x_i$ is for that argument in the converse -- of not one of $x_i$ or $x'_i$ being part of $X_2$ -- to work. Isn't it so? Can you please tell me what I'm missing? $\endgroup$ – anon. computer scientist Mar 10 '15 at 19:29

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.