# Subset-sum variation, multiple sums

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.

• 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? – Juho Nov 6 '15 at 6:36
• See cs.stackexchange.com/q/1240/755 and cs.stackexchange.com/q/11209/755 for our reference material on this topic. (Possible dup?) – D.W. Nov 6 '15 at 7:06
• @Juho Wouldn't that lead us to a Cook reduction (instead of Karp)? – Raphael Nov 6 '15 at 8:45
• @Raphael Yes, possibly. – 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.