The Class co-NP
co-NP contains problems whose no-answers have short, polynomial-time-checkable certificates.
The mirror of NP
A problem is in co-NP if its complement is in NP. Where NP has easily verified yes-instances, co-NP has easily verified no-instances: a short certificate proves the answer is no. The two classes are reflections of each other across the yes/no line.
A concrete example
"Is this Boolean formula unsatisfiable?" is in co-NP. If it is satisfiable (a no to unsatisfiability), a satisfying assignment is a short certificate of the no-answer. But there is no known short certificate that a formula is unsatisfiable, so the problem is not obviously in NP.
Tautologies and validity
- Tautology checking (is a formula true under all assignments) is in co-NP
- Primality was long known to be in NP and co-NP before being shown in P
- Any problem in P is in both NP and co-NP
The open question
Whether NP equals co-NP is open and widely believed false. If they differed, it would immediately follow that P is not NP, since P is closed under complement and lies in both. A proof that NP is not co-NP would be a partial resolution of the P vs NP puzzle.
NP-complete and co-NP
If any NP-complete problem were in co-NP, then NP would equal co-NP. This is considered unlikely, which is why researchers doubt that, say, SAT has short certificates of unsatisfiability.
Where the classes meet
The intersection NP and co-NP contains problems with short certificates for both yes and no answers. Such problems are considered unlikely to be NP-complete. Factoring's decision version sits here, one reason it is thought to be easier than the NP-complete problems even though no polynomial algorithm is known.