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$ 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

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


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.