## complementary nondeterministic polynomial

<*complexity*> (Co-NP) The set (or property) of problems with a
yes/no answer where the complementary no/yes problem takes
nondeterministic polynomial time (NP).

For example, "Is n prime" is Co-NP and "Is n not prime" is NP, since it is only necessary to find one factor to prove that n is not prime whereas to prove that it is prime all possible factors must be eliminated.

Last updated: 2009-05-21

Try this search on Wikipedia, OneLook, Google

**Nearby terms:**

**complementary nondeterministic polynomial**» complete » complete graph » complete inference system