8
$\begingroup$

I have a problem which I suspect is NP-complete. It is easy to prove that it is NP. My current train of thought revolves around using a reduction from knapsack but it would result in instances of 0-1-Knapsack with the value of every item being equal to its weight.

Is this still NP-complete? Or am I missing something?

|cite|improve this question
$\endgroup$
  • $\begingroup$ This is years too late, but anyway: Your wording suggests that you might be trying to reduce in the wrong direction. You need to reduce from knapsack to your problem, meaning that you have to allow arbitrary Knapsack instances (which may produce instances of your problem that have some special structure) -- no part of this procedure would "result in" Knapsack instances with some special structure. (OTOH, it does make sense to ask whether some special case of Knapsack is still NP-complete, since it might be easier to reduce from.) $\endgroup$ – j_random_hacker Feb 26 '16 at 1:25
  • $\begingroup$ Yes. What I meant was that I reduce from knapsack but specifically from the "0-1-Knapsack with the value of every item being equal to its weight". So, it was only my wording that was a little off. $\endgroup$ – Zeta Two Feb 26 '16 at 9:01
7
$\begingroup$

Yes, this is called the subset-sum problem and is NP-Hard.

|cite|improve this answer
$\endgroup$
  • $\begingroup$ Thanks! I just realized that I did that discovery earlier. Unfortunately I also realized that my reduction didn't work at all. Back to the drawing board. :( $\endgroup$ – Zeta Two Apr 12 '13 at 11:26
  • $\begingroup$ @ZetaTwo: You are welcome :-) $\endgroup$ – Aryabhata Apr 13 '13 at 18:29

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.