Co-NP

From Wikipedia

HomePage | Recent changes | View source | Discuss this page | Page history | Log in |

Printable version | Disclaimers | Privacy policy

In complexity theory, Co-NP is the complement of the class NP. For every decision problem in NP, Co-NP contains the same decision problem with the YES and NO answers swapped. Equivalently, for every language in NP, Co-NP contains the complement of that language.

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. 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.