Co-NP

The Television & Movie Wiki: for TV, celebrities, and movies.

In computational complexity theory, co-NP is a complexity class. A problem <math>\mathcal{X}</math> is a member of co-NP if and only if its complement <math>\overline{\mathcal{X}}</math> is in complexity class NP. In simple terms, co-NP is the class of problems for which efficiently verifiable proofs of no instances, sometimes called counterexamples, exist.

For example, there is an NP-complete problem called the subset-sum problem, which asks if any subset of a finite set of integers sums to zero. Its complement problem is in co-NP and asks if every subset sums to a nonzero number. A counterexample would be a subset which does sum to zero, which is easy to verify.

P is a subset of both NP and co-NP. That subset is thought to be strict in both cases. NP and co-NP are also thought to be unequal. If so, 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. Assume that there is an NP-complete problem that is in co-NP. Since all problems in NP can be reduced to this problem it follows that for all problems in NP we can construct a non-deterministic Turing machine that decides the complement of the problem in polynomial time, i.e., NP is a subset of co-NP. 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., co-NP is a subset of NP. Since we already knew that NP is a subset of co-NP it follows that they are the same. The proof for the fact that no co-NP-complete problem can be in NP is symmetrical.

If a problem can be shown to be in both NP and co-NP, that is generally accepted as strong evidence that the problem is probably not NP-complete (since otherwise NP = co-NP). One example is integer factorization, the problem of determining whether an integer n has a prime factor less than k. It is in both NP and co-NP, but is generally suspected to be outside P, outside NP-complete, and outside co-NP-complete.