Lower and Upper Bounds are Friends - Not Food

The other day I was working on a proof to show that there is a polynomial transformation from SUBSET-SUM-ZERO to SUBSET-SUM-ONE where the two problems are decision problems and are defined as follows:

1. SUBSET-SUM-ZERO: Given a list of integers, if there exists a non-empty subset of those integers that sum to $0$, return YES. Otherwise return FALSE.
2. SUBSET-SUM-ONE: Given a list of integers, if there exists a non-empty subset of those integers that sum to $1$, return YES. Otherwise return FALSE.

For a while, I had come up with a transformation $f(I)$ where I could show that if I had a instance $I$ that should evaluate to true for SUBSET-SUM-ZERO (SSZ), then there is one for $f(I)$ that evaluates true for SUBSET-SUM-ONE (SSO), but couldn’t find one to prove the backwards direction.

After some back and forth of modify/adding/removing parts of $f(I)$ to gain the ability to fix a structure for a subset sum in $f(I)$ which is $1$, I ended up with the transformation:

1. Define $P$ as the sum of all positive numbers in $I$ and $N$ as the sum of all negative numbers.
2. Define $K = P + |N| + 1$. The importance of the $+1$ will become apparent in setting up inequalities in the following sections.
3. Add $2x_i + 2K$ to the list generated by $f(I)$ where $x_i$ is an entry in $I$.
4. Add $n-1$ entries of $-2K$ to $f(I)$ where $n$ is the length of $I$.
5. Add $-2K + 1$ to $f(I)$.

Using this definition of $f(I)$ I was able to eliminate some possible structures for a subset of $f(I)$ that adds to $1$ (which I leave the elimination as an exercise to the reader 🙃) to be left with the only possible structure(s) being of the form:

where:

1. $2(x_e + ... + x_j) + j(2K)$ is some non-empty subset sum of elements in $f(I)$ that “come from” $I$ but are transformed. $j$ is the number of entries in $(x_e + ... + x_j)$.
2. $c(-2K)$ are some entries of $-2K$ where $0 \leq c \leq n - 1$.
3. $-2K + 1$ is the last entry, and must be included since it is the only non-odd entry.

After doing some rearranging and factoring, we are left with:

where $i = c + 1$. My goal here is to show that $x_e + ... + x_j$ sums to zero, which shows that $I$ contains a subset whose sum is zero.

The key observation is that the righthand side is some positive or negative multiple of $K = P + |N| + 1$. Then, the smallest positive value that can appear on the righthand side of the equation is $K = P + |N| + 1$ while the greatest negative number (closest to zero) is $-K = -(P + |N| + 1)$.

We know that the largest possible positive sum we can find in $I$ can only be as large as the sum of positive values in $I$, since any other value is either zero or reduces the sum as it is negative. Then we have $x_e + ... + x_j < K$ since $P < K = P + |N| + 1$. A same statement can be made about the greatest negative number to determine that $-K < x_e + ... + x_j$. This means that $-K < x_e + ... + x_j < K$ and $x_e + ... + x_j$ is a non-empty subset of $I$ that sums to a multiple of $K$. See where this is going? The only integer multiple of $K$ between $-K$ and $K$ is $0$, which means $x_e + ... + x_j$ is a non-empty sum of $I$ that sums to $0$ (as required).

To summarize: the reason we were able to deduce that the sum was zero was because we had (among some other choices of $f(I)$ to eliminate possible other structures) a choice of $K$ that has a lowest possible positive value and greatest possible negative value out of the range of values that any subset of $I$ could sum to. Finding these bounds is a very simple task (unlike the NP nature of the SSO and SSZ class of problems), which makes finding $K$ in polytime easy too.

This also highlights the nature of some problems that are NP (like finding whether a subset of given integers sum to a particular value), but related problems are in fact P (like finding the upper and lower bounds of the sum of a subset of given integers).