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?]
