coNP
Is NP = coNP ? 
In computational complexity theory, coNP is a complexity class. A decision problem is a member of coNP if and only if its complement is in the complexity class NP. In simple terms, coNP is the class of problems for which efficiently verifiable proofs of no instances, sometimes called counterexamples, exist. Equivalently, coNP is the set of decision problems where the "no" instances can be accepted in polynomial time by a nondeterministic Turing machine.
An example of an NPcomplete problem is the subset sum problem: given a finite set of integers, is there a nonempty subset that sums to zero? To give a proof of a "yes" instance, one must specify a nonempty subset that does sum to zero. The complementary problem is in coNP and asks: "given a finite set of integers, does every nonempty subset have a nonzero 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 coNP. 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 coNP are also thought to be unequal.^{1} If so, then no NPcomplete problem can be in coNP and no coNPcomplete problem can be in NP.
This can be shown as follows. Suppose there exists an NPcomplete problem that is in coNP. Since all problems in NP can be reduced to , it follows that for every problem in NP we can construct a nondeterministic Turing machine that decides its complement in polynomial time, i.e., NP ⊆ coNP. 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 coNP, i.e., coNP ⊆ NP. Thus coNP = NP. The proof that no coNPcomplete problem can be in NP, if NP ≠ coNP is symmetrical.
If a problem can be shown to be in both NP and coNP, that is generally accepted as strong evidence that the problem is probably not NPcomplete (since otherwise NP = coNP).
An example of a problem that is known to belong to both NP and in coNP 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 coNP 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 coNP problems. The AKS primality test, published in 2002, proves that primality testing also lies in P, while factorization may or may not have a polynomialtime algorithm.^{2}
References
 ^ Hopcroft, John E. (2000). Introduction to Automata Theory, Languages, and Computation (2nd Edition). Boston: AddisonWesley. ISBN 0201441241. Chap. 11.
 ^ Manindra Agrawal, Neeraj Kayal, Nitin Saxena, "PRIMES is in P", Annals of Mathematics 160 (2004), no. 2, pp. 781793.
External links

HPTS  Area Progetti  EduSoft  JavaEdu  N.Saperi  Ass.Scuola..  TS BCTV  TS VideoRes  TSODP  TRTWE  