# Why do I only need to reduce from one problem in NP to prove NP-Hardness?

Suppose I wish to show that my decision problem $$Q$$ is NP-Hard. Why do I need to reduce from one problem $$Q'$$ of known hardness ?

Consider for instance the following situation: Here, I have my set NP of problems, where problems $$A$$ and $$B$$ were proved to be NP-Complete through direct proof, and problems $$C$$, $$D$$, $$E$$, and $$Q'$$ were proved to be NP-Complete through reduction. I reduce from $$Q'$$ to $$Q$$, then later show $$Q$$ is in $$P$$. I agree that I then would be able to claim that problems $$Q'$$ and $$B'$$ can be claimed to also be in $$P$$, since we can just reduce them to $$Q$$. However, why can we make the same claims about $$C$$, $$D$$ and $$E$$ ? there is no (known) way of reducing from them to $$Q$$, we merely know that they may be "at least as hard" as the unlabeled problem and problem $$A$$, but can't it be possible that they are harder?

This is why intuitively, it seems to me like we should be showing ways to reduce from all "leaf" problems in NP, to show that $$Q$$ is also NP-Hard, even if I am told that this is not needed.

• can't it be possible that they are harder? No. NP-complete problems are the hardest problems in NP, by definition. Since $Q'$ is NP-complete and (by your assumption) lies in P, we know that any problem from NP ($E$ and $D$ in particular) lies in P. – Dmitry Nov 19 '20 at 1:12
• @Dmitry So when we are proving that a problem is NP-Hard (but isn't in NP), is it however correct to say that it is "at least as hard as the hardest problem in NP, but may be even harder" ? – – Pierre Duluth Nov 19 '20 at 1:46
• That's correct. E.g. it's easy to construct an undecidable NP-hard problem. – Dmitry Nov 19 '20 at 2:03
• Every NPC problem (in fact, every NP problem) can be reduced to any NPC problem in poly-time -- that's what NP-completeness means. The direct proofs for $A$ and $B$ must establish this somehow for these problems. So, there should be in-edges to $A$ and $B$ for every other problem in your diagram -- and thus a path of reductions from every problem to $Q$. – j_random_hacker Nov 19 '20 at 3:37