co-NP

In computational complexity theory, co-NP is a complexity class. A decision problem X is a member of co-NP if and only if its complement X is in the complexity class NP. The class can be defined as follows: a decision problem is in co-NP if and only if for every no-instance we have a polynomial-length "certificate" and there is a polynomial-time algorithm that can be used to verify any purported certificate.

That is, co-NP is the set of decision problems where there exists a polynomial ${\displaystyle p(n)}$ and a polynomial-time bounded Turing machine M such that for every instance x, x is a no-instance if and only if: for some possible certificate c of length bounded by ${\displaystyle p(n)}$, the Turing machine M accepts the pair (x, c).^[1]

Complementary Problems

While an NP problem asks whether a given instance is a yes-instance, its complement asks whether an instance is a no-instance, which means the complement is in co-NP. Any yes-instance for the original NP problem becomes a no-instance for its complement, and vice versa.

Unsatisfiability

An example of an

This section needs expansion with: examples of duals for decision/optimization problems in NP and co-NP. You can help by adding to it. (June 2021)

co-NP-completeness

A problem L is co-NP-complete if and only if L is in co-NP and for any problem in co-NP, there exists a polynomial-time reduction from that problem to L.

Tautology Reduction

Determining if a formula in

P, the class of polynomial time solvable problems, is a subset of both NP and co-NP. P is thought to be a strict subset in both cases (and demonstrably cannot be strict in one case and not strict in the other).^{[citation needed]}

NP and co-NP are also thought to be unequal.

${\displaystyle {\textsf {NP}}\subseteq {\textsf {co-NP}}}$

${\displaystyle {\textsf {co-NP}}\subseteq {\textsf {NP}}}$

${\displaystyle {\textsf {co-NP}}={\textsf {NP}}}$

${\displaystyle {\textsf {NP}}\neq {\textsf {co-NP}}}$

co-NP is a subset of PH, which itself is a subset of PSPACE.

Integer Factorization

An example of a problem that is known to belong to both NP and co-NP (but not known to be in P) is