# co-NP

Unsolved problem in computer science: |

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**. In simple terms, **co-NP** is the class of problems for which there is a polynomial-time algorithm that can verify *no* instances (sometimes called counterexamples) given the appropriate certificate. Equivalently, **co-NP** is the set of decision problems where the "no" instances can be accepted in polynomial time by a non-deterministic Turing machine.

An example of an **NP**-complete problem is the subset sum problem: given a finite set of integers, is there a non-empty subset that sums to zero? To give a proof of a "yes" instance, one must specify a non-empty subset that does sum to zero. The complementary problem is in **co-NP** and asks: "given a finite set of integers, does every non-empty subset have a non-zero sum?".

## Relationship to other classes[edit]

**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). **NP** and **co-NP** are also thought to be unequal.^{[1]} If so, then no **NP**-complete problem can be in **co-NP** and no **co-NP**-complete problem can be in **NP**.^{[2]}

This can be shown as follows. Suppose there exists an **NP**-complete problem X that is in **co-NP**. Since all problems in **NP** can be reduced to X, 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., **NP** ⊆ **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** ⊆ **NP**. Thus **co-NP** = **NP**. The proof that no **co-NP**-complete problem can be in **NP** if **NP** ≠ **co-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 that is known to belong to both **NP** and **co-NP** is integer factorization: given positive integers *m* and *n* determine if *m* has a factor less than *n* and greater than one. Membership in **NP** is clear; if *m* does have such a factor then the factor itself is a certificate. Membership in **co-NP** is also straightforward: one can just list the prime factors of *m*, all greater or equal to n, which the verifier can confirm to be valid by multiplication and the AKS primality test. It is presently not known whether there is a polynomial-time algorithm for factorization, equivalently that integer factorization is in **P**, and hence this example is interesting as one of the most natural problems known to be in **NP** and **co-NP** but not known to be in **P**.^{[3]}

## References[edit]

**^**Hopcroft, John E. (2000).*Introduction to Automata Theory, Languages, and Computation (2nd Edition)*. Boston: Addison-Wesley. ISBN 0-201-44124-1. Chap. 11.**^**Goldreich, Oded (2010).*P, NP, and NP-completeness: The Basics of Computational Complexity*. Cambridge University Press. p. 155. ISBN 9781139490092.**^**http://mathoverflow.net/q/31821