Co-NP

From Wikipedia, the free encyclopedia

List of unsolved problems in computer science
Is NP = co-NP* ?*

In computational complexity theory, co-NP is a complexity class. A decision problem ${{\mathcal {X}}}$ is a member of co-NP if and only if its complement $\overline {{\mathcal {X}}}$ 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 the case of co-NP but not the NP). r). 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 ${{\mathcal {X}}}$ that is in co-NP. Since all problems in NP can be reduced to ${{\mathcal {X}}}$ , 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

↑ Hopcroft, John E. (2000). Introduction to Automata Theory, Languages, and Computation (2nd Edition). Boston: Addison-Wesley. ISBN 0-201-44124-1. Chap. 11.
↑ Manindra Agrawal, Neeraj Kayal, Nitin Saxena, "PRIMES is in P", Annals of Mathematics 160 (2004), no. 2, pp. 781-793.

External links

Complexity Zoo: coNP

v t e Important complexity classes (more)

Considered feasible	DLOGTIME AC⁰ ACC⁰ TC⁰ L SL RL NL NC SC CC P P-complete ZPP RP BPP BQP

Suspected infeasible	UP NP NP-complete NP-hard co-NP co-NP-complete AM PH ⊕P PP #P #P-complete IP PSPACE PSPACE-complete

Considered infeasible	EXPTIME NEXPTIME EXPSPACE ELEMENTARY PR R RE ALL

Class hierarchies	Polynomial hierarchy Exponential hierarchy Grzegorczyk hierarchy Arithmetical hierarchy Boolean hierarchy

Families of classes	DTIME NTIME DSPACE NSPACE Probabilistically checkable proof Interactive proof system

This article is issued from Wikipedia. The text is available under the Creative Commons Attribution/Share Alike; additional terms may apply for the media files.