Non-Deterministic Algorithm
Jump to navigation
Jump to search
A Non-Deterministic Algorithm is a algorithm that may not always produces the same algorithm output for a given algorithm input.
- …
- Counter-Example(s):
- See: Non-Deterministic, Non-Deterministic Running-Time, Randomized Algorithm, Non-Deterministic Turing Machine, Concurrent Algorithm, Race Condition, Probabilistic Algorithm, Random Number Generator, Nondeterministic Polynomial Time.
References
2016
- (Wikipedia, 2016) ⇒ http://wikipedia.org/wiki/Nondeterministic_algorithm Retrieved:2016-1-28.
- In computer science, 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.
The notion was introduced by Robert W. Floyd.
- In computer science, 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.