### NP time ==>

# non-deterministic polynomial time

<*complexity*> (NP) A set or property of computational decision
problems solvable by a non-deterministic Turing Machine in a
number of steps that is a polynomial function of the size of
the input. The word "non-deterministic" suggests a method of
generating potential solutions using some form of
non-determinism 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 non-deterministic 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?]

[FOLDOC]

<*2001-03-16*>

Try this search on OneLook / Google

**Nearby terms:**
non-determinism « non-deterministic « non-deterministic automaton « non-deterministic polynomial time » non-deterministic Turing Machine » nonlinear » non parity