# There is equivalence in an NP-hardness proof or not?

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$

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.
• 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? – npisinp Mar 3 '14 at 22:46
• @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. – David Richerby Mar 3 '14 at 23:16