Equivalence of two definitions of SUBSET-SUM

Question

Consider one version of the subset sum problem: given a target $W$ and positive integers $a_1, a_2,..,a_n$, decide whether there exists a nonempty subset $S \subset [n]$ so that $\sum_{i \in S} a_{i}=W$. Let us call this version $A$. The other version is: given integers $a_1, a_2,...,a_n$, decide whether there exists a nonempty subset $S \subset [n]$ so that $\sum_{i \in S} a_i=0$. Let us call this version $B$.

It is relatively easy to reduce version $A$ to version $B$. If $W = 0$, the reduction is immediate. Otherwise add $-W$ into the set of numbers and call version $B$.

Is there a "natural" way to reduce version $B$ to version $A$?

One approach is arguing that version $A$ is NP-complete and version $B$ is in NP, so the result follows from the definition of NP-Completeness, but this doesn't seem "natural" to me and seems to use more machinery (e.g., the Cook-Levin theorem) than needed. The problems should be similar enough that there is a natural correspondence between them.

Answer 1

Here is a polynomial-time reduction from version B to $n$ instances of version $A$.

Let $b_1,\dots,b_n$ be the integers in an instance of version B.

• Choose an integer $M$ so that $|b_i| < M$ for all $1\le i\le n$.
• Then choose an integer $B>(n+1)M$; note that this inequality implies that if $1\le t\le n$ then $(t+1)(B-M) > tB$ and $(t-1)(B+M) < tB$.

Now define $a_i=b_i+B$ for every $1\le i\le n$; note that $B-M \le a_i \le B+M$ for all $1\le i\le n$.

Use version A to determine whether there are solutions $S$ to $\sum_{i\in S} a_i=tB$, for every $1\le t\le n$.

Suppose we find a solution to a particular $\sum_{i\in S} a_i = tB$.

• If $S$ had at least $t+1$ elements, then $\sum_{i\in S} a_i \ge (t+1)(B-M) > tB$, a contradiction.
• Similarly if $S$ had at most $t-1$ elements, then $\sum_{i\in S} a_i \ge (t-1)(B+M) < tB$, a contradiction.
• It follows that $S$ has exactly $t$ elements, whence $\sum_{i\in S} b_i = \sum_{i\in S} (a_i-B) = \sum_{i\in S} a_i - tB = 0$ is a solution to the original instance of version B.

And of coures, any solution $\sum_{i\in S} b_i = 0$ with $\#S=t$ immediately gives rise to the solution $\sum_{i\in S} a_i = tB$, so we are guaranteed to detect any solution of the version B instance in this way.