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?
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.
Sign up to join this communityIf 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?
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.)