[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