# Is the NP-hardness Proof with One Way Implication Correct and Why?

A problem $\Pi$ is NP-hard if I can prove this:

• a known NP-hard problem $\Pi'$ reduces to $\Pi$ in polynomial time; and
• $f(x) \in \Pi\iff$ $x \in \Pi'$.

If I can show only one way implication, that is $f(x) \in \Pi\Rightarrow$ $x \in \Pi'$. Is this reduction known, correct and why?

For me it is correct because, if I had an algorithm for $\Pi$ then I would use it to solve $\Pi'$. Therefore, $\Pi$ is at least as hard as $\Pi'$ then $\Pi$ is NP-hard.

• "I had an algorithm for Π then I would use it to solve Π′" -- except you wouldn't know that the answer would be correct! – Raphael Feb 23 '16 at 11:53
• @Raphael I think that your edit "corrects" one main source of confusion. Indeed, the last paragraph doesn't make much sense now. – Yuval Filmus Feb 23 '16 at 11:57
• I only changed tags; you'll have to talk to @Shreesh. I did not notice that earlier; I can see now where your answer came from. Sorry about that. – Raphael Feb 23 '16 at 12:57
• @Yuval, In my edit, I did mention, that I seek permission from OP to make the changes. I am sorry for that. If the original question from OP makes any sense then we can revert the question back. – Shreesh Feb 23 '16 at 13:02
• @Shreesh Well, the original question also didn't make any sense. Presumably the OP was a bit confused. – Yuval Filmus Feb 23 '16 at 13:11

Consider the following two wrong "reductions" from $SAT$ to $L = \{1\}$. Let $\phi$ be a $SAT$ instance.

We "reduce" every $\phi$ to 1, i.e. $f(\phi) = 1$. Now we have $\phi \in SAT \Rightarrow 1 \in L$. But $L$ is clearly not NP-hard.

Next we "reduce" every $\phi$ to 0, i.e. $f(\phi) = 0$. Now we have $0\in L \Rightarrow \phi \in SAT$. But again $L$ is clearly not NP-hard.

Thus we can see that for a correct reduction we need a proper if and only if condition: $x \in \Pi' \Leftrightarrow f(x) \in \Pi$.

If we have a reduction as above, and if we know that SAT is NP-complete (in other words a hard problem), we have two corollaries from this.

1) Any language can be reduced to SAT. So every language can be reduced to SAT and then to $L$, so $L$ is also NP-complete (now we know that $L$ must also be a hard problem).

2) Any algorithm for membership of $L$ can be used to solve membership to SAT. So if we have an "algorithm" for $L$ then so do we have an "algorithm" for SAT. The algorithm will work this way. From $\phi$ we will construct $f(\phi)$ and then apply our "algorithm" to $f(\phi)$. If answer is YES then $\phi$ is also satisfiable, and if answer is NO then $\phi$ is not satisfiable.

So from 2) we can see that an algorithm for $L$ is applicable for $SAT$. But vice versa is not true. Any algorithm for $SAT$ (polynomial or exponential) can not be used for $L$ using this reduction (there might be other ways but not using just the above reduction). Notice the uncovered region in $L$. So this is what is meant by cryptic comment: solution of $L$ $\Rightarrow$ solution of SAT.

• Thank you. I do not understand how $0\in L\Rightarrow\phi\in SAT$. See this example: I will reduce $SAT$ to INDEPENDENT SET. Given an instance of $SAT$, a Boolean formula $\phi$. Create an instance of INDEPENDENT SET, a graph $G$ and an integer $k$. Now, I showed that $G$ has an independent set of size $k$ $\Rightarrow$ $\phi$ is satisfiable. If INDEPENDENT SET is in P then I could use my reduction and show that SAT is also in P. – 1-approximation Feb 23 '16 at 9:14
• I gave two wrong reductions one for which $x \in \Pi' \Rightarrow f(x) \in \Pi$ and other for which $x \in \Pi' \Leftarrow f(x) \in \Pi$. – Shreesh Feb 23 '16 at 12:58
• Furthermore, if your constructed $G$ does not have an independent set of size $k$ then would you be able to say that $\phi$ is unsatisfiable? You won't. So you don't get full solution of SAT problem. – Shreesh Feb 23 '16 at 13:24
• @1-approximation That comment is in the wrong place. Either ask David for clarification over there (ask him a question!) or post a new question altogether. – Raphael Feb 23 '16 at 20:02
• @1-approximation I am glad you understood it. You can delete the thank you comments and any other irrelevant comments now. – Shreesh Feb 24 '16 at 13:36