To prove that a problem $\Pi_2$ is NP-hard one has to:

  1. select a known NP-hard problem $\Pi_1$;
  2. from an arbitrary instance of $\Pi_1$, create an instance of $\Pi_2$ in polynomial-time; and
  3. 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?


1 Answer 1


No, you may not modify $I_1$. By the time you get to Step 3, everything is determined and you might not change your instances. Say $f$ is the polytime transformation from Step 2. Then you need to show

$I_1$ is a yes-instance of $\Pi_1$ if and only if $f(I_1) = I_2$ is a yes-instance of $\Pi_2$.

If after arriving at Step 3 you notice that your $I_2$ instance does not allow you to prove the statement, then you might want to change $f$ in your Step 2, and redo Step 3.


Your Answer

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

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