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.
Is the problem NP-C or polynomially solvable?
np complete;subset sum
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$ nonemptyand 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$