2
$\begingroup$

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.

$\endgroup$

1 Answer 1

2
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ Brilliant! Thanks. $\endgroup$ Dec 24, 2021 at 3:10
  • $\begingroup$ With $K = |T| +\sum\limits_{i=1}^n|a_i|$, isn't there a counter-example with $(-1, -1)$ and $T = 1$? Here, $K = 3$, and $(2, 2, 3, 3)$ with $T = 7$ is a positive instance. $\endgroup$
    – Nathaniel
    Jan 23 at 17:41
  • $\begingroup$ If think you just need to add a $+1$ in the definition of $K$. $\endgroup$
    – Nathaniel
    Jan 23 at 17:52

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.