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.

$\endgroup$
  • $\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 '16 at 16:49
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 .

$\endgroup$
  • $\begingroup$ "Due to dynamic programming, one would prove ​ P = NP" Sorry, could you elaborate on this? $\endgroup$ – Moeghoeg Apr 24 '16 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 '16 at 14:27
  • $\begingroup$ Oh. That makes sense. My bad! $\endgroup$ – Moeghoeg Apr 24 '16 at 14:43

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.