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 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 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, the Turing machine M accepts the pair.
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 NP-complete problem is the Boolean satisfiability problem: given a Boolean formula, is it satisfiable ? The complementary problem asks: "given a Boolean formula, is it unsatisfiable ?". Since this is the complement of the satisfiability problem, a certificate for a no-instance is the same as for a yes-instance from the original NP problem: a set of Boolean variable assignments which make the formula true. On the other hand, a certificate of a yes-instance for the complementary problem would be equally as complex as for the no-instance of the original NP satisfiability problem.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 propositional logic is a tautology is co-NP-complete: that is, if the formula evaluates to true under every possible assignment to its variables.Relationship to other classes
Image:Complexity-classes-polynomial.svg|thumb|Inclusions of complexity classes including P, NP, co-NP, BPP, P/poly, PH, and PSPACEP, 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. Because P is closed under complementation, and NP and co-NP are complementary, it cannot be strict in one case and not strict in the other: if P equals NP, it must also equal co-NP, and vice versa.
NP and co-NP are also thought to be unequal, and their equality would imply the collapse of the polynomial hierarchy PH to NP. If they are unequal, then no NP-complete problem can be in co-NP and no co-NP-complete problem can be in NP. This can be shown as follows. Suppose for the sake of contradiction there exists an NP-complete problem that is in co-NP. Since all problems in NP can be reduced to, it follows that for every problem in NP, we can construct a non-deterministic Turing machine that decides its complement in polynomial time; i.e.,. From this, it follows that the set of complements of the problems in NP is a subset of the set of complements of the problems in co-NP; i.e.,. Thus. The proof that no co-NP-complete problem can be in NP if is symmetrical.
co-NP is a subset of PH, which itself is a subset of PSPACE.