Nondeterministic algorithm
|
|
In the theory of computation, a nondeterministic algorithm is a hypothetical algorithm where computation can branch, choosing among different execution paths in a way that does not depend only on the input and current execution state. A nondeterministic algorithm can produce different outputs or final states when run repeatedly with the same input.
In standard usage, in fact, an algorithm means a deterministic algorithm. There are, however, models of computation, such as the nondeterministic finite state machine, that use non-determinism.
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 Powerset construction for this technique in use for finite automata).
Randomization is a way of transforming a nondeterministic algorithm into a probabilistic deterministic algorithm.
Here is an example of a non-deterministic algorithm for testing if an integer n is prime.
- Guess an integer k such that 2 ≤ k ≤ n-1.
- If k is a divisor of n, stop with answer no; otherwise stop with answer don't know.
It is seen that the algorithm doesn't always give a useful answer, but never gives a wrong answer. Also, it is capable (at least sometimes) of giving a correct useful answer much faster than any deterministic primality algorithm.