Karp reduction from NP-hard problem to unknown problem

Question

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?

Answer 1

Short answer, yes. I won't provide an actual proof (you probably saw one in class), but rather, a sort of mnemonic that helps if this comes up on an exam.

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.)