1
$\begingroup$

I want to show that a problem is NP-hard by reducing a known NP-complete problem to it. However, I will have to use a special case of the NP-complete problem for the reduction to work. I'm pretty sure that the special case version is also NP-complete but I have no idea how to prove that. Are there any general guidelines for how to do this?

For example, consider this version of the SUBSET SUM problem without repetition:

Given an integer I and a multiset S of integers in the range 1,2,...,10, is there a non-empty subset of S whose sum is I?

I could be wrong, but don't think the restriction of possible values in S to {1, ..., 10} affects the NP-completeness of the problem. How would one go about showing this?

EDIT: Apparently that version of the problem is actually in P. I might restate my question later.

Improve this question
$\endgroup$
1
  • $\begingroup$ There aren't really any general guidelines for proving that something is NP-complete, beyond trying to reduce from a similar-looking problem that is known to be NP-complete. Proving things requires creativity and there's no algorithm for coming up with proofs. $\endgroup$
    – David Richerby
    Apr 24, 2016 at 16:49

1 Answer 1

Reset to default
1
$\begingroup$

"Are there any general guidelines for how to do this?"

Frequently, one does that by reducing from the general case to the special case.
Otherwise, being a special case of a known NP-complete problem isn't really helpful for that.


How would one go about showing this?

Due to dynamic programming, one would prove ​ P = NP .

Improve this answer
$\endgroup$
3
  • $\begingroup$ "Due to dynamic programming, one would prove ​ P = NP" Sorry, could you elaborate on this? $\endgroup$
    – Moeghoeg
    Apr 24, 2016 at 14:25
  • $\begingroup$ SUBSET SUM is NP-complete, but by dynamic programming, that "version of the SUBSET SUM problem" is in P, so if "the restriction of possible values in S" does not affect "the NP-completeness of the problem" then ​ P = NP . ​ ​ ​ ​ $\endgroup$
    – user12859
    Apr 24, 2016 at 14:27
  • $\begingroup$ Oh. That makes sense. My bad! $\endgroup$
    – Moeghoeg
    Apr 24, 2016 at 14:43

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.