# Is the problem NP-C or polynomially solvable?

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.

• en.wikipedia.org/wiki/Partition_problem – R B Nov 25 '14 at 13:10
• 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. – Tom van der Zanden Nov 25 '14 at 13:47
• 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. – Marzio De Biasi Nov 25 '14 at 13:59
• @MarzioDeBiasi, comment --> answer? – usul Nov 25 '14 at 18:28
• @Tom van der Zanden: Could you elaborate on the “little trickery”? It is believable such modification can be done, but I cannot see how. – Tsuyoshi Ito Nov 25 '14 at 19:59

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: (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$

• 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? – anon. computer scientist Mar 10 '15 at 17:20
• @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. – Marzio De Biasi Mar 10 '15 at 19:04
• 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? – anon. computer scientist Mar 10 '15 at 19:29