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$