How to reduce SUBSET-SUM with integers to SUBSET-SUM with non-negative integers?

Question

The subset sum problem is as follows:

Given a sequence of integers $\mathcal S=(a_1, ..., a_n)$ with cardinality $n$ and an integer $T$, determine whether there is a subsequence of $\mathcal S$ whose sum equals $T$. Denote this problem $SSP$.

I was given a variant of the subset sum problem:

Given a sequence of $\color{blue}{\mbox{non-negative}}$ integers $\mathcal S=(a_1, ..., a_n)$ with cardinality $n$ and an integer $T$, determine whether there is a subsequence of $\mathcal S$ whose sum equals $T$. Denote this problem $SSP_+$.

My task is to prove that $$SSP\leq_p SSP_+$$ Therefore, I have to come up with a polynomial-time transformation $f$ between problem instances of $SSP$ and those of $SSP_+$, and prove the correctness of my reduction. This is where I encounter difficulties. I was given a hint:

Let $L=(a_1,\cdots,a_n;T)$ be a problem instance of $SSP$, then consider a transformation $f$ in the sense that $$f(a_1,\cdots,a_n;T)=(a_1+K,\cdots,a_n+K, \underbrace{K, \cdots,K}_{n\,K's};T+nK)$$ How do you choose $K$? And, when do you need to do the transformation? Don’t forget to justify that the answer to the problem instance $L$ is “yes” iff the answer to $f(L)$ is “yes”.

---

My Thoughts

I was thinking about assigning $K$ the value $$K=\sum_{i=1}^n|a_i|$$ so that there is no subsequence of $\mathcal S$ whose sum exceeds $K$. This $K$ ensures that $a_i+K\geq 0$ for $1\leq i\leq n$.

To me it's rather straightforward to show that $$\mbox{answer to }L\mbox{ is "yes"}\implies \mbox{answer to }f(L)\mbox{ is "yes"}$$ but I encounter serious difficulties proving the other direction. That's why I come here to seek help.

---

My Questions

Is my choice of $K$ correct? If so, how do I prove the other direction?

---

Thanks for reading my post.

Answer 1

To prove the reverse direction you need to show that if there exist a subsequence $S_1$ in $(a_1+K,a_2+K,\dotsc,a_n+K,K,\dotsc,K)$ that sums to $T+nK$, then there is a subsequence $S_2$ in $(a_1,\dotsc,a_n)$ that sums to $T$.

The proof would become easy if we assume that $S_1$ only contains $n$ elements. If that happens, then the above statement holds. (hope you can prove this on your own).

Now, we need to make sure that $S_1$ contains exactly $n$ elements for its sum to be $T+nK$. Note that it is possible when $K$ is super large. If $K$ is super large and $S_1$ contains more than $n$ elements, then sum of $S_1$ $>$ $T+nK$. Similarly, if $K$ is super large and $S_1$ contain less than $n$ elements, then sum of $S_1$ $<$ $T+nK$.

Therefore, better choose $K$ to be at least $|T| + \sum_{i = 1}^n|a_i|$.

---

Your choice of $K$ is problematic. For example, consider sequence $(-1,-1)$ and $T=2$ (which is a no instance). Here $K = \sum_{i = 1}^n |a_i| = 2$. This sequence reduces to sequence $(1,1,2,2)$ and $T = 6$, which is a yes instance.