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$
Improve this question
$\endgroup$

1 Answer 1

Reset to default
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.

Improve this answer
$\endgroup$
5
  • $\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, 2014 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, 2014 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, 2016 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, 2016 at 1:15
  • $\begingroup$ This is very helpful. Thank you for your time. $\endgroup$
    – 1-approximation
    Feb 24, 2016 at 2:04

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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