nondeterministic polynomial time
<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)
Nearby terms:
nondeterminism « nondeterministic « nondeterministic
automaton « nondeterministic polynomial time
» Nondeterministic Turing Machine » non-impact
printer » non-interlaced
|
