Take the 2-minute tour ×
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.

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

share|improve this question

2 Answers 2

up vote 10 down vote accepted

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.

share|improve this answer
    
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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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