# Co-NP

Is
NP = co-NP ? |

In computational complexity theory, **co-NP** is a complexity class. A decision problem is a member of **co-NP** if and only if its complement is in the 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. 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?" This problem is not obviously seen to be in **NP**.

## Relationship to other classes

**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**.

This can be shown as follows. Suppose 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., **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 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. 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*, which the verifier can confirm to be valid by multiplication and the AKS primality test.

Integer factorization is closely related to the primality problem. Both primality testing and factorization have long been known to be **NP** and **co-NP** problems. The AKS primality test, published in 2002, proves that primality testing also lies in **P**, while factorization may or may not have a polynomial-time algorithm.^{[2]}

## References

- ↑ {{#invoke:citation/CS1|citation |CitationClass=book }} Chap. 11.
- ↑
Manindra Agrawal, Neeraj Kayal, Nitin Saxena, "PRIMES is in P",
*Annals of Mathematics*160 (2004), no. 2, pp. 781-793.

## External links

{{#invoke: Navbox | navbox }}