Subset-sum problem is NP-complete. I presume so is the problem of determining, given a positive integer $p$, whether in a set of positive integers $\{x_1,x_2,...,x_n\}$ there is a subset which sums to one of the numbers $\{p-1,p,p+1\}$. Am I correct?

I've been struggling to reduce standard Subset-sum to this variation, but for no good so far. Can you see any other reduction? Or could give me a hint on this one? Perhaps I'm fixed for that Subset-sum and don't some other obvious possibility.

  • $\begingroup$ Intuitively, suppose you had an efficient algorithm for this new problem. Using this supposed algorithm, can you solve the subset sum problem efficiently as well? $\endgroup$ – Juho Nov 6 '15 at 6:36
  • 1
    $\begingroup$ See cs.stackexchange.com/q/1240/755 and cs.stackexchange.com/q/11209/755 for our reference material on this topic. (Possible dup?) $\endgroup$ – D.W. Nov 6 '15 at 7:06
  • $\begingroup$ @Juho Wouldn't that lead us to a Cook reduction (instead of Karp)? $\endgroup$ – Raphael Nov 6 '15 at 8:45
  • $\begingroup$ @Raphael Yes, possibly. $\endgroup$ – Juho Nov 6 '15 at 8:49

Hint: Given an instance $\{x_1,\ldots,x_n\},T$ of SUBSET-SUM, construct the instance $\{2x_1,\ldots,2x_n\},2T$ of your problem.

  • $\begingroup$ I haven't thought of that :( Smart, thank you. $\endgroup$ – Jules Nov 6 '15 at 14:40

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.