# Karp reduction from NP-hard problem to unknown problem

If I know that problem $$A$$ is NP-hard, but know nothing of problem $$B$$ and I know that the following Karp reduction is true:

$$A \to B \, .$$

Is it correct to conclude that $$B$$ must also be NP-hard?

• What do you think? This must have been covered in class. – Yuval Filmus Dec 16 '18 at 0:37
• I think it is true, was just hoping for a confirmation. – wazus Dec 16 '18 at 0:38
• Why do you think it's true? Can you prove it? – Yuval Filmus Dec 16 '18 at 0:39
• Well, my understanding is that the thing on the right hand side of a reduction is at least as hard as the thing on left side. Sorry I'm not so bright.. – wazus Dec 16 '18 at 0:41
• Hopefully you've seen a proof in class. Otherwise, it's a travesty. – Yuval Filmus Dec 16 '18 at 0:42

A Karp reduction is also known as a polynomial-time reduction. If you can reduce from $$A$$ to $$B$$, that means if I give you a subroutine that solves $$B$$, you can build an algorithm to solve $$A$$, which does at most polynomial-time work and then calls the $$B$$ subroutine to get the answer.
The question is now, if you can reduce from $$A$$ to $$B$$, and $$A$$ is $$NP$$-hard, then is $$B$$ $$NP$$-hard?
Assume it isn't. In other words, assume $$B$$ can be solved in polynomial time. Then that means $$A$$ can be solved in polynomial time: run the polynomial-time reduction, call $$B$$ which takes polynomial time, and you have a solution to $$A$$ in polynomial time. We've proven $$P = NP$$ and earned a million dollars!
Since we haven't proven anything of the sort, our assumption must be false. In other words, $$B$$ must be NP-hard.
(Now, this would be a formal proof if $$P \neq NP$$ were a known result. But it isn't. So while this is good enough to remember on an exam, and the fact that $$B$$ must be $$NP$$-hard is in fact true, I haven't actually given a full proof of that fact.)