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.

1. Guess an integer k such that 2 ≤ k ≤ n-1.
2. 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.