from
The Free On-line Dictionary of Computing (8 July 2008)
nondeterministic polynomial time
NP 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)