World's most popular travel blog for travel bloggers.

Does coNP-completeness imply NP-hardness?

, , No Comments
Problem Detail: 

Does coNP-completeness imply NP-hardness? In particular, I have a problem that I have shown to be coNP-complete. Can I claim that it is NP-hard? I realize that I can claim coNP-hardness, but I am not sure if that terminology is standard.

I am comfortable with the claim that if an NP-complete problem belonged to coNP, then NP=coNP. However, these lecture notes state that if an NP-hard problem belongs to coNP, then NP=coNP. This would then suggest that I cannot claim that my problem is NP-hard (or that I have proven coNP=NP, which I highly doubt).

Perhaps, there is something wrong with my thinking. My thought is that a coNP-complete problem is NP-hard because:

  1. every problem in NP can be reduced to its complement, which will belong to coNP.
  2. the complement problem in coNP reduces to my coNP-complete problem.
  3. thus we have a reduction from every problem in NP to my coNP-complete, so my problem is NP-hard.
Asked By : Austin Buchanan

Answered By : Yuval Filmus

You claim that every problem in NP can be reduced to its complement, and this is true for Turing reductions, but (probably) not for many-one reductions. A many-one reduction from $L_1$ to $L_2$ is a polytime function $f$ such that for all $x$, $x \in L_1$ iff $f(x) \in L_2$.

If some problem $L$ in coNP were NP-hard, then for any language $M \in NP$ there would be a polytime function $f$ such that for all $x$, $x \in M$ iff $f(x) \in L$. Since $L$ is in coNP, this gives a coNP algorithm for $M$, showing that NP$\subseteq$coNP, and so NP$=$coNP. Most researchers don't expect this to be the case, and so problems in coNP are probably not NP-hard.

The reason we use Karp reductions rather than Turing reductions is so that we can distinguish between NP-hard and coNP-hard problems. See this answer for more details (Turing reductions are called Cook reductions in that answer).

Finally, coNP-hard and coNP-complete are both standard terminology, and you are free to use them.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/16371

0 comments:

Post a Comment

Let us know your responses and feedback