<p>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 <a href="http://en.wikipedia.org/wiki/Partition_problem" rel="nofollow noreferrer">PARTITION</a>. 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 <a href="http://www.sciencedirect.com/science/article/pii/002001909290226L" rel="nofollow noreferrer">EQUAL-SUBSET-SUM</a> problem.</p>

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

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

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

<p>The following figure should make things clearer:</p>

<p><img src="https://i.sstatic.net/eUYRN.png" alt="enter image description here"><br>
(empty cells represent zeros)</p>

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

<p>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 <em>subtract</em> 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$</p>

CC BY-SA 3.0
2015-03-10T17:20:26.250Z
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
CC BY-SA 3.0
2015-03-10T19:04:18.283Z
@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
CC BY-SA 3.0
2015-03-10T19:29:13.347Z
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
CC BY-SA 3.0
2014-11-25T22:58:52.810Z
2014-11-25T22:58:52.810Z
Marzio De Biasi
<p>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$)</p>

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

CC BY-SA 3.0
2014-11-25T13:10:07.750Z
http://en.wikipedia.org/wiki/Partition_problem
R B
CC BY-SA 3.0
2014-11-25T13:47:54.500Z
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
CC BY-SA 3.0
2014-11-25T13:59:02.020Z
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](http://www.sciencedirect.com/science/article/pii/002001909290226L) which is still NPC.
Marzio De Biasi
CC BY-SA 3.0
2014-11-25T18:28:08.587Z
@MarzioDeBiasi, comment --> answer?
usul
CC BY-SA 3.0
2014-11-25T19:59:26.040Z
@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
<np-complete><subset-sum>
Is the problem NP-C or polynomially solvable?
An Zhang
# Is the problem NP-C or polynomially solvable?

(Asked by: username_0 on 2014-11-25)

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.

**Tags:** np-complete, subset-sum
> **Comments:**
> **username_1**: http://en.wikipedia.org/wiki/Partition_problem  
> **username_2**: 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.  
> **username_3**: 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](http://www.sciencedirect.com/science/article/pii/002001909290226L) which is still NPC.  
> **username_4**: @MarzioDeBiasi, comment --> answer?  
> **username_5**: @Tom van der Zanden: Could you elaborate on the “little trickery”?  It is believable such modification can be done, but I cannot see how.  

---

## 1 answers

### Answer by username_3 on 2014-11-25. Score: 7 | Accepted answer

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](http://en.wikipedia.org/wiki/Partition_problem). 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](http://www.sciencedirect.com/science/article/pii/002001909290226L) 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](https://i.sstatic.net/eUYRN.png)  
(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$

> **Comments:**
> **username_6**: 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?  
> **username_3**: @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.  
> **username_6**: 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?  

---

