You are here: irt.org | FOLDOC | 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.
(2009-05-21)
Nearby terms: COMPL « complement « Complementary Metal Oxide Semiconductor « complementary nondeterministic polynomial » complete » complete graph » complete inference system
FOLDOC, Topics, A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R, S, T, U, V, W, X, Y, Z, ?, ALL