- Co-NP
In

computational complexity theory ,**co-NP**is acomplexity class . A problem $mathcal\{X\}$ is a member of**co-NP**if and only if its complement $overline\{mathcal\{X$ 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 thesubset 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 known to be in

**NP**and in**co-NP**isinteger 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 more subtle; one must list the prime factors of "m" and provide aprimality certificate for each one.Integer factorization is often confused with the closely relatedprimality problem. Both primality testing and factorization have long been known to be**NP**and**co-NP**problems. TheAKS primality test , published in 2002, proves that primality testing also lies in**P**, while factorization may or may not have a polynomial-time algorithm. [*Manindra Agrawal, Neeraj Kayal, Nitin Saxena, " [*]*http://www.cse.iitk.ac.in/users/manindra/algebra/primality_v6.pdf PRIMES is in P*] ", "Annals of Mathematics" 160 (2004), no. 2, pp. 781�793.**References****External links*** Complexity Zoo: [

*http://qwiki.caltech.edu/wiki/Complexity_Zoo#conp coNP*]

*Wikimedia Foundation.
2010.*