Non-deterministic_algorithm
Nondeterministic algorithm
Algorithm whose behavior and output may depend on the run
In computer programming, a nondeterministic algorithm is an algorithm that, even for the same input, can exhibit different behaviors on different runs, as opposed to a deterministic algorithm. There are several ways an algorithm may behave differently from run to run. A concurrent algorithm can perform differently on different runs due to a race condition. A probabilistic algorithm's behaviors depends on a random number generator. An algorithm that solves a problem in nondeterministic polynomial time can run in polynomial time or exponential time depending on the choices it makes during execution. The nondeterministic algorithms are often used to find an approximation to a solution, when the exact solution would be too costly to obtain using a deterministic one.
This article may be confusing or unclear to readers. In particular, the word "nondeterministic" is used with two different meanings. (January 2022) |
The notion was introduced by Robert W. Floyd in 1967.[1]