Word:

nondeterministic polynomial time

(complexity)nondeterministic polynomial time - (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.

Browse
noncurrent
noncyclic
noncyclical
Nonda
Nondecane
Nondeciduate
nondecisive
nondeductible
Nondelivery
nondenominational
Nondeposition
nondepository financial institution
nondescript
nondeterminism
nondeterministic
nondeterministic automaton
-- nondeterministic polynomial time --
Nondeterministic Turing Machine
Nondevelopment
nondigestible
nondirectional antenna
Nondiscovery
nondiscretionary trust
nondiscrimination
nondisjunction
nondisposable
Nondo
nondrinker
nondriver
nondurable
None
None of
None-so-pretty
Index: # 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

About this site and copyright information - Online Dictionary Home