nondeterministic polynomial time

complexity (NP) A set or property of computational decisionproblems 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 polynomialtime) 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)