-1
$\begingroup$

Lets say there is an reduction in polynomial time from problem A to B, from problem B to C and from problem C to D. Now lets say C is NP hard. Does this mean A,B,D are NP hard as well?

$\endgroup$
  • 1
    $\begingroup$ I suggest you refresh the basic definitions and remember the intuition that X reduces to Y means that solving Y is at least as hard as solving X. $\endgroup$ – David Richerby May 31 at 7:33
2
$\begingroup$

There exists a reduction (many-to-one polynomial time) from a problem (or language) $A$ to a problem $B$, denoted $A \leq_{\textsf{p}}^{\textsf{m}} B$, if there exists a function $f$, computable in polynomial time in the size of the entry, so that $x\in A \Leftrightarrow f(x) \in B$.

It means that if you are able to solve any instance of the problem $B$, then for an instance $x$ of the problem $A$, you can transform it into $f(x)$, solve it like a problem of $B$, and it gives you the answer for the instance $x$.

In your case, if $A \leq_{\textsf{p}}^{\textsf{m}} B \leq_{\textsf{p}}^{\textsf{m}} C \leq_{\textsf{p}}^{\textsf{m}} D$ and $C$ is $\textsf{NP}$-hard, then it implies that $D$ is $\textsf{NP}$-hard. But if $C$ is $\textsf{NP}$, it implies that $A$ and $B$ are $\textsf{NP}$ (since hardness gives a lower bound and $\textsf{NP}$ gives an upper bound).

You can find a reference in the Arora-Barak, page 59 of the pdf, or the Cormen-Leiserson-Rivest-Stein, page 992 of the pdf.

$\endgroup$
  • $\begingroup$ So if $C$ is NP hard, it only implies that $D$ is in NP. It does not tell anything about $A$ and $B$ right? $\endgroup$ – gamma May 31 at 8:46
  • $\begingroup$ Yup, that's it! $\endgroup$ – Nathaniel May 31 at 18:48

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.