0
$\begingroup$

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.

Improve this question
$\endgroup$
4
  • $\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
    Commented Nov 6, 2015 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. ♦
    Commented Nov 6, 2015 at 7:06
  • $\begingroup$ @Juho Wouldn't that lead us to a Cook reduction (instead of Karp)? $\endgroup$
    – Raphael
    Commented Nov 6, 2015 at 8:45
  • $\begingroup$ @Raphael Yes, possibly. $\endgroup$
    – Juho
    Commented Nov 6, 2015 at 8:49

1 Answer 1

Reset to default
1
$\begingroup$

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.

Improve this answer
$\endgroup$
1
  • $\begingroup$ I haven't thought of that :( Smart, thank you. $\endgroup$
    – Jules
    Commented Nov 6, 2015 at 14:40

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.