1
$\begingroup$

I want to show that some problem $P_1$ is NP-hard. I have a problem $P_2$ that is NP-complete. From an instance of $P_2$ I created in polynomial time an instance of the problem $P_1$.

My question is: Should I verify both direction ($\Leftrightarrow$) or only one direction ($\Rightarrow$)? More precisely, which one to show from these two:

  • Solve $P_1\;\Leftrightarrow$ solve $P_2$
  • Solve $P_1\;\Rightarrow$ solve $P_2$
$\endgroup$
2
$\begingroup$

You only need to show that solving $P_1$ allows you to solve $P_2$ (and, hence, every other problem in NP).

$P_1$ might not be in NP so it's not necessarily the case that solving $P_2$ allows you to solve $P_1$. On the other hand, if $P_1$ is in NP, then you already know that solving $P_2$ allows you to solve $P_1$, by definition of NP-completeness.

$\endgroup$
  • $\begingroup$ Great thanks. As I understand, if I was showing that $P_1$ is NP-complete instead of NP-hard, then I had to show the equivalence. Am I correct? $\endgroup$ – npisinp Mar 3 '14 at 22:46
  • 1
    $\begingroup$ @npisinp NP-completeness just means that it's NP-hard and in NP. So, to show it's NP-complete, you just show those two things. You get equivalence with $P_2$ "for free" from the fact that they're both NP-complete, so you don't need to prove it separately. $\endgroup$ – David Richerby Mar 3 '14 at 23:16
  • $\begingroup$ I asked this question yesterday cs.stackexchange.com/questions/53495/… and the answers say that I should prove the iff not only one way. Can you clarify please? $\endgroup$ – 1-approximation Feb 23 '16 at 20:49
  • $\begingroup$ @1-approximation You're asking about a completely different situation. You're asking about whether it's enough to define the notion of reduction using "if" rather than "if and only if"; this question is about whether, given the standard definition of reduction, you need to establish reductions both ways between a pair of problems or just one way. $\endgroup$ – David Richerby Feb 24 '16 at 1:15
  • $\begingroup$ This is very helpful. Thank you for your time. $\endgroup$ – 1-approximation Feb 24 '16 at 2:04

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.