2
$\begingroup$

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?

Improve this question
$\endgroup$
5
  • $\begingroup$ If it is true can you suggest a paper which does such claims? $\endgroup$
    – user14178
    Commented Mar 13, 2013 at 14:16
  • 1
    $\begingroup$ 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). $\endgroup$
    – Magnus Find
    Commented Mar 13, 2013 at 14:39
  • $\begingroup$ 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? $\endgroup$
    – user14178
    Commented Mar 13, 2013 at 14:56
  • $\begingroup$ If you understand the definition of NP-hardness, then you should be able to answer your question yourself. $\endgroup$
    – Yuval Filmus
    Commented Mar 14, 2013 at 4:25
  • $\begingroup$ See our reference question. $\endgroup$
    – Raphael
    Commented Mar 14, 2013 at 7:39

3 Answers 3

Reset to default
5
$\begingroup$

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?

Improve this answer
$\endgroup$
3
$\begingroup$

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?

Improve this answer
$\endgroup$
2
$\begingroup$

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

Improve this answer
$\endgroup$

Your Answer

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