23
$\begingroup$

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

$\endgroup$

2 Answers 2

28
$\begingroup$

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.

$\endgroup$
3
  • 12
    $\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, 2013 at 3:37
  • 3
    $\begingroup$ Yep, good point! $\endgroup$
    – usul
    Feb 15, 2013 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, 2013 at 2:35
4
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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