nondeterministic polynomial time

Computing Dictionary

nondeterministic polynomial time definition

complexity
(NP) A set or property of computational decision problems solvable by a nondeterministic Turing Machine in a number of steps that is a polynomial function of the size of the input. The word "nondeterministic" suggests a method of generating potential solutions using some form of nondeterminism or "trial and error". This may take exponential time as long as a potential solution can be verified in polynomial time.
NP is obviously a superset of P (polynomial time problems solvable by a deterministic Turing Machine in polynomial time) since a deterministic algorithm can be considered as a degenerate form of nondeterministic algorithm. The question then arises: is NP equal to P? I.e. can every problem in NP actually be solved in polynomial time? Everyone's first guess is "no", but no one has managed to prove this; and some very clever people think the answer is "yes".
If a problem A is in NP and a polynomial time algorithm for A could also be used to solve problem B in polynomial time, then B is also in NP.
See also Co-NP, NP-complete.
[Examples?]
(1995-04-10)
The Free On-line Dictionary of Computing, © Denis Howe 2010 http://foldoc.org
Cite This Source
Explore Dictionary.com
More from Thesaurus.com
Synonyms and Antonyms for nondeterministic polynomial time
More from Reference.com
Search for articles containing nondeterministic polynomial time
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