co-NP
Unsolved problem in computer science: Is NP = co-NP ? (more unsolved problems in computer science) |
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. Instances of decision problems in co-NP are sometimes called "counterexamples". In simple terms, co-NP is the class of problems for which efficiently verifiable proofs of "no" instances exist. Equivalently, co-NP is the set of decision problems where the "no" instances can be solved in polynomial time by a theoretical 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
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 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).
Integer factorization is closely related to the primality problem. An integer factorization algorithm can decide primality. The contrary is not true: for a primality test it is enough to show that a factor exists when checking a composite number. 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.[3] Factorization may or may not have a polynomial-time algorithm.
References
- ↑ 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.
- ↑ Manindra Agrawal, Neeraj Kayal, Nitin Saxena, "PRIMES is in P", Annals of Mathematics 160 (2004), no. 2, pp. 781-793.