4
$\begingroup$

SSUM is the same as the Subset Sum Problem with the only additional requirement is all the numbers must be unique in the subset.

To prove it's NP complete, the verifier is quite easy to construct being the same as one for the Subset Sum except you add the additional requirement of making sure all numbers are unique.

With the reduction, I assume you can use the same reduction as before from 3SAT, I'm just figuring out a way when evaluating that reduction, to determine if two or more numbers are the same. I'm using the 3SAT reduction in Sipser with the table of columns and rows. If one needs any more information I would be happy to provide.

Improve this question
$\endgroup$
2
  • $\begingroup$ Yes, please do provide more information in the question. What have you tried? Have you tried seeing if you can make the reduction for Subset-Sum work? Does it work as-is, or are modifications needed? If it doesn't work as-is, why not (what specifically goes wrong?), and what kinds of tweaks to that reduction have you tried? Also, have you tried reducing from Subset-Sum rather than reducing from 3SAT? We ask you to show us what you've tried, where you got stuck, and a specific question -- rather than just copying your exercise and asking us to solve it for you. $\endgroup$ – D.W.♦ Dec 11 '13 at 20:17
  • $\begingroup$ well i used the same reduction as subset-sum which i hope is universal. I just wanna know if i can interpret that reduction to determine if two numbers are the same $\endgroup$ – Jen Stone Dec 11 '13 at 20:41
5
$\begingroup$

One way to show that SSUM is NP-hard is by reduction from SUBSET-SUM. The idea is to replace each number $n_i$ by two numbers $Mn_i + \epsilon_i$ and $\epsilon_i$, where $M$ is a "large" integer and $\epsilon_i$ is a "small" integer. By varying $\epsilon_i$ you ensure that all numbers are different. You set your target at $MT+\delta$, where $T$ is the original target and $\delta = \sum_i \epsilon_i$. Further details left to you.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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