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.

  • 8
    $\begingroup$ 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. $\endgroup$ – vzn Feb 15 '13 at 3:37
  • 3
    $\begingroup$ Yep, good point! $\endgroup$ – usul Feb 15 '13 at 3:45
  • 2
    $\begingroup$ as an addition to that though, just saw an assertion in a paper that NP=coNP is widely believed. $\endgroup$ – 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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.