# show that special case of NP-complete problem is also NP-complete?

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.

• 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. Apr 24 '16 at 16:49

"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 .

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