[Solved]: CoNP and NPhard intersection

Problem Detail: Can a problem be both NP-Hard and CoNP? Can a problem be both NP and CoNP-Hard?

Asked By : Turbo

Answered By : Peter Shor

There is a problem which is both NP-hard and in coNP if and only if NP = coNP. If NP = coNP, than NP-complete problems (like 3-SAT) are both NP-hard and in coNP. On the other hand, if any NP-hard problem is in coNP, then all problems in NP are reducible to it, so all problems in NP are in coNP so NP ⊆ coNP. Now, since the complement of NP is coNP, and vice versa, we also have coNP ⊆ NP. This means NP = coNP. The question of whether NP = coNP is open, but most theoretical computer scientists do not think it is very likely.
Best Answer from StackOverflow

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