1
$\begingroup$

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.

$\endgroup$
3
  • $\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, 2018 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, 2018 at 11:49
  • $\begingroup$ It should be noted that the sets do not contain duplicate integers in both problems. $\endgroup$
    – AphexTwin
    Dec 20, 2018 at 12:03

1 Answer 1

2
$\begingroup$

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?

$\endgroup$

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.