I'm trying to learn reduction. I have this problem called "even subset sum" that's very similar to subset sum. It's the same problem as as subset sum except that the only numbers allowed are even positive integers. I'm trying to show this problem is NP-hard by reducing the problem subset sum to it but I'm not sure where to start.

  • $\begingroup$ Please state your problem, "even subset sum" in its full detail, assuming there is no prior knowledge of subset sum at all. $\endgroup$ – John L. Dec 20 '18 at 11:04
  • $\begingroup$ Given a set S of even positive integers and an integer k, is there a subset of S whose sum equals k? $\endgroup$ – AphexTwin Dec 20 '18 at 11:49
  • $\begingroup$ It should be noted that the sets do not contain duplicate integers in both problems. $\endgroup$ – AphexTwin Dec 20 '18 at 12:03

Hint: suppose that we are able to solve your problem efficiently. Then what if we take an arbitrary subset sum problem and multiply all elements by $2$, as well as the target?


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.