# Is the open question NP=co-NP the same as P=NP?

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...

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.

• also if NP$\neq$coNP then P$\neq$NP because P is closed under complement. so the question NP$\stackrel{?}{=}$coNP may be as hard as the infamous P$\stackrel{?}{=}$NP problem. – vzn Feb 15 '13 at 3:37
• Yep, good point! – usul Feb 15 '13 at 3:45
• as an addition to that though, just saw an assertion in a paper that NP=coNP is widely believed. – vzn Feb 16 '13 at 2:35

One good way to answer this question is to use the polynomial hierarchy (PH) (see also here). The polynomial hierarchy is a hierarchy of complexity classes that generalizes the classes ${\sf P}$, ${\sf NP}$ and ${\sf co-NP}$ to oracle machines and use as a scale to measure complexity of problems.

It is known that If ${\sf NP}={\sf co-NP}$ or ${\sf P}={\sf NP}$ then the polynomial hierarchy collapses to its first level.