# If a problem C is NP hard and there is an existing reduction from/to A,B,D, are they NP hard as well?

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?

• 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. – David Richerby May 31 at 7:33

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).
• So if $C$ is NP hard, it only implies that $D$ is in NP. It does not tell anything about $A$ and $B$ right? – gamma May 31 at 8:46