2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ "I had an algorithm for Π then I would use it to solve Π′" -- except you wouldn't know that the answer would be correct! $\endgroup$ – Raphael Feb 23 '16 at 11:53
  • $\begingroup$ @Raphael I think that your edit "corrects" one main source of confusion. Indeed, the last paragraph doesn't make much sense now. $\endgroup$ – Yuval Filmus Feb 23 '16 at 11:57
  • $\begingroup$ 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. $\endgroup$ – Raphael Feb 23 '16 at 12:57
  • $\begingroup$ @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. $\endgroup$ – Shreesh Feb 23 '16 at 13:02
  • $\begingroup$ @Shreesh Well, the original question also didn't make any sense. Presumably the OP was a bit confused. $\endgroup$ – Yuval Filmus Feb 23 '16 at 13:11
5
$\begingroup$

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$.

enter image description here

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.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – 1-approximation Feb 23 '16 at 9:14
  • $\begingroup$ 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$. $\endgroup$ – Shreesh Feb 23 '16 at 12:58
  • $\begingroup$ 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. $\endgroup$ – Shreesh Feb 23 '16 at 13:24
  • $\begingroup$ @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. $\endgroup$ – Raphael Feb 23 '16 at 20:02
  • $\begingroup$ @1-approximation I am glad you understood it. You can delete the thank you comments and any other irrelevant comments now. $\endgroup$ – Shreesh Feb 24 '16 at 13:36

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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