Nondeterministic algorithm
This article may be confusing or unclear to readers. In particular, the word "nondeterministic" is used with two different meanings. (January 2022) |
In
The notion was introduced by Robert W. Floyd in 1967.[1]
Use
Often in
In algorithm design, nondeterministic algorithms are often used when the problem solved by the algorithm inherently allows multiple outcomes (or when there is a single outcome with multiple paths by which the outcome may be discovered, each equally preferable). Crucially, every outcome the nondeterministic algorithm produces is valid, regardless of which choices the algorithm makes while running.
In computational complexity theory, nondeterministic algorithms are ones that, at every possible step, can allow for multiple continuations (imagine a person walking down a path in a forest and, every time they step further, they must pick which fork in the road they wish to take). These algorithms do not arrive at a solution for every possible computational path; however, they are guaranteed to arrive at a correct solution for some path (i.e., the person walking through the forest may only find their cabin if they pick some combination of "correct" paths). The choices can be interpreted as guesses in a search process.
A large number of problems can be conceptualized through nondeterministic algorithms, including the most famous unresolved question in computing theory,
Implementing nondeterministic algorithms with deterministic ones
One way to simulate a nondeterministic algorithm N using a deterministic algorithm D is to treat sets of states of N as states of D. This means that D simultaneously traces all the possible execution paths of N (see
Another is
See also
References
- ^
Robert W.Floyd (October 1967). "Nondeterministic Algorithms". S2CID 1990464.
Further reading
- Cormen, Thomas H. (2009). Introduction to Algorithms (3rd ed.). MIT Press. ISBN 978-0-262-03384-8.
- "Nondeterministic algorithm". National Institute of Standards and Technology. Retrieved July 7, 2013.
- "Non-deterministic Algorithms". New York University Computer Science. Retrieved July 7, 2013.