To prove that a problem $\Pi_2$ is NP-hard one has to:
- select a known NP-hard problem $\Pi_1$;
- from an arbitrary instance of $\Pi_1$, create an instance of $\Pi_2$ in polynomial-time; and
- show that solve $\Pi_1$ with the given instance $\iff$ solve $\Pi_2$ with the created instance.
Now, my question is the following.
Suppose now I did 1., 2. and only solve $\Pi_1\Rightarrow$ solve $\Pi_2$ but when I am trying to show the inverse, i.e., solve $\Pi_2\Rightarrow$ solve $\Pi_1$, the instance of $\Pi_1$ is changed a little. Is this proof correct?
More precisely, let $I_1=(n, a_1,\ldots,a_n,b_1,\ldots,b_n,\alpha,\beta,k)$ be an arbitrary instance of $\Pi_1$. The created instance (in polynomial-time) of $\Pi_2$ is $I_2=(n, a_1,\ldots,a_n,b_1,\ldots,b_n,\Delta,k)$. Now when I tried to show solve $\Pi_2$ with $I_2\Rightarrow$ solve $\Pi_1$ with $I_1$, I found another instance of $\Pi_1$, $I_1'=(n, a_1,\ldots,a_n,b_1,\ldots,b_n,a,b,k)$ where $a\neq \alpha$ and $b\neq\beta$. Hence I did not solve $\Pi_1$ with $I_1$ but with $I_1'$.
My guess is that the proof still correct, right?