# Does hardness of a special case imply hardness of a general case?

I am wondering in general if it is correct to claim that if a special case of a problem is NP-Hard, the general case of that problem is NP- Hard too?

For example: Min Set-Cover is NP-Hard does it imply without having to prove that Min Set-k-Cover where each element needs to be covered k times is NP-Hard too?

• If it is true can you suggest a paper which does such claims?
– user14178
Mar 13, 2013 at 14:16
• You should perhaps be a bit more clear what you mean by "the general case". Your example indicates a particular problem where some parameter is constant. If this is what you mean it is not true. A simple example is k-clique, that easily admits a $n^k$ algorithm (try all subsets).
– Magnus Find
Mar 13, 2013 at 14:39
• True I am not being clear. I don't mean a constant parameter when I mean general case. What I mean by special case is really a special instance of the problem with some restrictions. To modify the example, if I prove that Min Set-Cover is NP-Hard with lets say fixed set sizes does it imply that Min Set-Cover is NP-Hard without any restriction on set sizes?
– user14178
Mar 13, 2013 at 14:56
• If you understand the definition of NP-hardness, then you should be able to answer your question yourself. Mar 14, 2013 at 4:25
• – Raphael
Mar 14, 2013 at 7:39

## 3 Answers

If frafl's answer doesn't give it away immediately, perhaps think in the reverse direction, if the special case is NP-hard, what would be implied by the general case being in P?

To show that a general problem $G=\{(w,k)\mid \text{Property}\}$ is NP-complete you need a polynomial time computable many-one reduction function $f$ from e.g. $S_l =\{w\mid (w,l) \in G\}$ to $G$. How could $f$ look like?

A problem is a set of instances. We consider a problem "hard" if there are instances that require lots of resources to solve (time, space, brain cells, whatever). If a subset of the problem is hard, then the problem is hard. If a subset is easy, that doesn't mean the problem is easy (there might be hard instances elsewhere). Think of the hardness as a "worst possible case" measure.

[Yes, I know this is horribly non-rigorous.]