Co-NP

From Wikipedia, the free encyclopedia

In computational complexity theory, co-NP is a complexity class. A problem is a member of co-NP if and only if its complement 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.

An example of an NP-complete problem is the subset-sum problem: given a finite set of integers is there a non-empty subset which sums to zero? The complementary problem is in co-NP and asks: given a finite set of integers does every non-empty subset have a nonzero sum? To give a proof of a "no" instance one must specify a non-empty subset which does sum to zero. This proof is then easy to verify.

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 but not the other). 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).

An example of a problem which is know to be in NP and in co-NP is integer factorization: given positive integers m and n determine if m has a factor less than n and greater than one. One direction is clear; if m does have such a factor then long division is a certificate. The other direction is slightly more subtle; one must list the prime factors of m and provide a primality certificate for each one.

Integer factorization is often confused with the closely related primality problem. This was also known to be in NP and co-NP, just as factorization is. However primality lies in P. See: http://www.math.princeton.edu/~annals/issues/2004/Sept2004/Agrawal.pdf

[edit] References

• Complexity Zoo: coNP

Important complexity classes (more)
P • NP • co-NP • NP-C • co-NP-C • NP-hard • UP • #P • #P-C • L • NL • NC • P-C • PSPACE • PSPACE-C • EXPTIME • EXPSPACE • PR • RE • Co-RE • RE-C • Co-RE-C • R • BQP • BPP • RP • ZPP • PCP • IP • PH