1
$\begingroup$

To prove that a problem is NP-complete, one has to show that it is both (a) in NP and that it is (b) NP-hard by reducing a known NP-complete problem to it in polynomial time.

Regarding the reduction, I understand that the instance of the known NP-complete problem must be arbitrary to avoid loss of generalisation.

Does the instance of the target problem also need to be arbitrary or can one assume specific values to its inputs to make the reduction easier?

Also, if one can assume specific values and carry out the reduction/proof, does the proof also hold for an arbitrary instance of the target problem?

From my understanding, if a specific instance of the target problem is proven to be NP-hard via reduction, then an arbitrary instance of the same problem is at least as hard as its specific instance, thus also NP-hard. Is this logically/mathematically sound?

Improve this question
$\endgroup$

1 Answer 1

Reset to default
6
$\begingroup$

A specific instance is never NP-hard. The concept of NP-hardness only applies to languages (classes of instances, if you will).

If your reduction from $A$ to $B$ is $f$, then $f$ is a function from the set of instances of $A$ to the set of instances of $B$. The function does not need to be injective nor surjective.

If $A$ is a NP-hard problem and you have a (Karp) reduction $f$ from $A$ to $B$, then the restriction of $B$ in which the instances are guaranteed to be in the image of $f$ is also NP-Hard. Since this is a (not necessarily proper) subset of all instances of $B$, the language $B$ is also NP-Hard.

Improve this answer
$\endgroup$
2
  • 1
    $\begingroup$ This is genuinely enlightening. So from my understanding of your explanation, one should restrict a family of instances of $B$ under a common rule (or language) and prove that, under this restriction, $A$ can be reduced to $B$ through $f$. Thanks :) $\endgroup$
    – pcko1
    May 30 at 18:13
  • 1
    $\begingroup$ @pkco1. I prefer to think this way: you just need to come up with a way (a polynomial-time computable function $f$) that transforms an (arbitrary) instance $x$ of $A$ into an instance $y=f(x)$ of $B$ (such that $x$ is a yes-instance iff $y$ is a yes-instance). There is no need to explicitly argue abut which subset of the instances of $B$ you'll actually need to map to (they'll be implicitly defined by $f$ but, if the goal is that of proving the hardness of $B$, you don't need to care about that). $\endgroup$
    – Steven
    May 31 at 7:24

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.