Problem Detail: I’m wondering this based on several places online that call $sf NP=$ co-$sf NP$ a major open problem… but I can’t find any indication as to whether or not this is the same as $sf P=NP$ problem…
Asked By : agent154
Answered By : usul
No. It is another open problem and certainly related, but different. The complexity class co-$mathsf{NP}$ is the set of languages whose complements are in $mathsf{NP}$; that is, the set of decision problems for which a “no” answer has a deterministic polynomial-time verifier. So for example, the question “Is this SAT formula unsatisfiable?” If the answer is “no”, then there is some satisfying assignment of the variables that proves this; that’s the certificate for the verifier. It is possible that $mathsf{P} neq mathsf{NP}$, yet $mathsf{NP} = $co-$mathsf{NP}$. But on the other hand, if $mathsf{P} = mathsf{NP}$, then $mathsf{NP} = $co-$mathsf{NP}$ for sure. This is because if a language is in $mathsf{P}$, then its complement is also in $mathsf{P}$, so if $mathsf{P} = mathsf{NP}$, then that goes for every language in $mathsf{NP}$ as well.
Best Answer from StackOverflow
Question Source : http://cs.stackexchange.com/questions/9795