Co-NP
Encyclopedia
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 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? To give a proof of a "yes" instance, one must specify a non-empty subset which 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 nonzero sum?" To give a proof of a "no" instance one must specify a non-empty subset which does sum to zero, which is easily verified.
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.
Computational complexity theory
Computational complexity theory is a branch of the theory of computation in theoretical computer science and mathematics that focuses on classifying computational problems according to their inherent difficulty, and relating those classes to each other...
, co-NP is a complexity class
Complexity class
In computational complexity theory, a complexity class is a set of problems of related resource-based complexity. A typical complexity class has a definition of the form:...
. A problem
is a member of co-NP if and only if its complementComplement (complexity)
In computational complexity theory, the complement of a decision problem is the decision problem resulting from reversing the yes and no answers. Equivalently, if we define decision problems as sets of finite strings, then the complement of this set over some fixed domain is its complement...
is in the complexity class NPNP (complexity)
In computational complexity theory, NP is one of the most fundamental complexity classes.The abbreviation NP refers to "nondeterministic polynomial time."...
. 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
NP-complete
In computational complexity theory, the complexity class NP-complete is a class of decision problems. A decision problem L is NP-complete if it is in the set of NP problems so that any given solution to the decision problem can be verified in polynomial time, and also in the set of NP-hard...
problem is the subset sum problem: given a finite set of integers is there a non-empty subset which sums to zero? To give a proof of a "yes" instance, one must specify a non-empty subset which 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 nonzero sum?" To give a proof of a "no" instance one must specify a non-empty subset which does sum to zero, which is easily verified.
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
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...
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
Non-deterministic Turing machine
In theoretical computer science, a Turing machine is a theoretical machine that is used in thought experiments to examine the abilities and limitations of computers....
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
Integer factorization
In number theory, integer factorization or prime factorization is the decomposition of a composite number into smaller non-trivial divisors, which when multiplied together equal the original integer....
: 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
Primality certificate
In mathematics and computer science, a primality certificate or primality proof is a succinct, formal proof that a number is prime. Primality certificates allow the primality of a number to be rapidly checked without having to run an expensive or unreliable primality test...
for each one.
Integer factorization
Integer factorization
In number theory, integer factorization or prime factorization is the decomposition of a composite number into smaller non-trivial divisors, which when multiplied together equal the original integer....
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
AKS primality test
The AKS primality test is a deterministic primality-proving algorithm created and published by three Indian Institute of Technology Kanpur computer scientists, Manindra Agrawal, Neeraj Kayal, and Nitin Saxena, on August 6, 2002, in a paper titled "PRIMES is in P"...
, published in 2002, proves that primality testing also lies in P, while factorization may or may not have a polynomial-time algorithm.