Recall that a *nondeterministic computation* can be viewed in either of two ways:

- When a choice point is reached, an infallible
*oracle*can be consulted to determine the correct choice. - When a choice point is reached,
*all*choices can be made and computation can proceed simultaneously.

A *nondeterministic polynomial-time algorithm* is an algorithm that can be
executed in polynomial time on a nondeterministic machine. The machine can either consult
an oracle (in constant time), or it can spawn an arbitrarily large number of parallel
processes.

It should be obvious that this would be a nice machine to have.

Copyright © 1996 by David Matuszek

Last modified Apr 28, 1996