Encyclopedia > Co-NP

  Article Content

Co-NP

In complexity theory, co-NP is the complexity class that contains the complements of decision problems in the complexity class NP. The complement of a decision problem is here defined as the problem with the yes and no answers reversed, or if we define decision problems as sets of finite strings as the complement of this set with respect to the given alphabet. From this definition it follows that the complement of every decision problem in NP is in co-NP and the complement of every decision problem in co-NP is in NP.

P is a subset of both NP and co-NP. That subset is thought to be strict in both cases. 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. One example is integer factorization, the problem of finding the prime factors of a number. It is in both NP and co-NP, but is generally suspected to be outside P, outside NP-complete, and outside co-NP-complete.



All Wikipedia text is available under the terms of the GNU Free Documentation License

 
  Search Encyclopedia

Search over one million articles, find something about almost anything!
 
 
  
  Featured Article
Islip Terrace, New York

... couples living together, 11.5% have a female householder with no husband present, and 16.6% are non-families. 13.2% of all households are made up of individuals and ...

 
 
 
This page was created in 24.4 ms