Co-nondeterministic polynomial-time

The complement class of NP: a decision problem is in coNP if its complement (swapping “yes” and “no” answers) is in NP. Equivalently, coNP is the class of problems for which a “no” answer can be verified in polynomial time given an appropriate certificate.

See the complexity zoo entry here.

Known relationships

• $\mathbf{P}\subseteq \mathbf{coNP}$, since P is closed under complement.
• If a problem is NP-complete, then it is in $\mathbf{coNP}$ if and only if $\mathbf{NP}=\mathbf{coNP}$.
• $\mathbf{coNP}\subseteq \mathbf{AM}$: this follows from the result of GS86 showing that coNP has Arthur-Merlin protocols.
• Integer factorization and discrete logarithm are both in $\mathbf{NP}\cap \mathbf{coNP}$: there are short certificates for both “yes” and “no” answers. This is one reason these problems are considered unlikely to be NP-complete — an NP-complete problem in coNP would imply $\mathbf{NP}=\mathbf{coNP}$.
• $\mathbf{coNP}\subseteq \mathbf{PSPACE}$.

Notable problems

• Tautology: given a Boolean formula, is every assignment satisfying? (The complement of SAT, which is NP-complete.)
• Graph non-isomorphism: are two graphs non-isomorphic? This problem is in coNP (and also in $\mathbf{SZK}$ and $\mathbf{coAM}$).
• Composite number: given $n$, does $n$ have a non-trivial factor? This is in both NP and coNP (primality testing is in $\mathbf{P}$ — TODO citation).