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