[Overview] [Previous] [Next]

Nondeterministic Polynomial-Time Algorithms

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

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