Co-NP

In computational complexity theory, co-NP is a complexity class. A problem $mathcal\left\{X\right\}$ is a member of co-NP if and only if its complement $overline\left\{mathcal\left\{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 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 known 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. 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 a primality certificate for each one.

Integer factorization is often confused with the closely related 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. [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

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

Wikimedia Foundation. 2010.

Look at other dictionaries:

• co-NP — Unsolved problems in computer science Is NP = co NP ? 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 the complexi …   Wikipedia

• Co-NP — In der Komplexitätstheorie bezeichnet Co NP eine Komplexitätsklasse. In ihr sind genau die Sprachen enthalten, deren Komplemente zu NP gehören. Die Klasse Co NP besteht also aus den Sprachen, für die ein Beweis, dass ein Wort nicht zur Sprache… …   Deutsch Wikipedia

• Co-NP — En teoría de la complejidad computacional, la clase de complejidad co NP es el conjunto de los problemas de decisión complementarios a los de la clase NP. Por problema complementario se entiende aquel que cuyas respuestas positiva o negativa… …   Wikipedia Español

• Co-NP — En teoría de la complejidad computacional, la clase de complejidad co NP es el conjunto de los problemas de decisión complementarios a los de la clase NP. Por problema complementario se entiende aquel que cuyas respuestas positiva o negativa… …   Enciclopedia Universal

• Co-Np — …   Википедия

• Co-NP — …   Википедия

• co-NP-complete — In complexity theory, computational problems that are co NP complete are those that are the hardest problems in co NP, in the sense that they are the ones most likely not to be in P. If there exists a way to solve a co NP complete problem quickly …   Wikipedia

• Co-NP-complete — In complexity theory, computational problems that are Co NP complete are those that are the hardest problems in Co NP, in the sense that they are the ones most likely not to be in P. If there exists a way to solve a Co NP complete problem quickly …   Wikipedia

• Co-NP (Komplexitätsklasse) — Dieser Artikel oder Abschnitt bedarf einer Überarbeitung. Näheres ist auf der Diskussionsseite angegeben. Hilf mit, ihn zu verbessern, und entferne anschließend diese Markierung. In der Komplexitätstheorie bezeichnet Co NP eine Komplexitätsklasse …   Deutsch Wikipedia

• Co-NP-completo — En teoría de la complejidad computacional, la clase de complejidad co NP completo es el conjunto de los problemas de decisión más difíciles de la clase co NP, en el sentido que son los que menos parecen pertenecer a la clase de complejidad P. De… …   Wikipedia Español