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?
$\begingroup$
$\endgroup$
7
-
$\begingroup$ What do you think? This must have been covered in class. $\endgroup$ – Yuval Filmus Dec 16 '18 at 0:37
-
$\begingroup$ I think it is true, was just hoping for a confirmation. $\endgroup$ – wazus Dec 16 '18 at 0:38
-
$\begingroup$ Why do you think it's true? Can you prove it? $\endgroup$ – Yuval Filmus Dec 16 '18 at 0:39
-
$\begingroup$ 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.. $\endgroup$ – wazus Dec 16 '18 at 0:41
-
$\begingroup$ Hopefully you've seen a proof in class. Otherwise, it's a travesty. $\endgroup$ – Yuval Filmus Dec 16 '18 at 0:42
|
Show 2 more comments
$\begingroup$
$\endgroup$
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.)
