complementary nondeterministic polynomial

Computing Dictionary

complementary nondeterministic polynomial definition

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)

The Free On-line Dictionary of Computing, © Denis Howe 2010 http://foldoc.org
Cite This Source
Dictionary.com Word FAQs

Dictionary.com presents 366 FAQs, incorporating some of the frequently asked questions from the past with newer queries.

Copyright © 2014 Dictionary.com, LLC. All rights reserved.
  • Please Login or Sign Up to use the Recent Searches feature