NONDETERMINISTIC ALGORITHM

In the theory of computation, a 'nondeterministic algorithm' is an algorithm with one or more choice points where multiple different continuations are possible, without any specification of which one will be taken. A particular execution of such an algorithm picks a choice whenever such a point is reached. Thus, different execution paths of the algorithm arise when it is applied to the same input / initial state, and these paths, when they terminate, generally produce different output / end in different final states.

Contents

Use

Turning nondeterministic algorithms into deterministic ones

Examples

Example 1: Spanning tree computation

Example 2: Primality testing

See also

Use

In the standard theory of computation, the term algorithm stands for a deterministic algorithm. However, it employs models of computation, such as the nondeterministic finite state machine, that use nondeterminism.
In algorithm design, nondeterministic algorithms are often used as specifications.

Turning nondeterministic algorithms into 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 Powerset construction for this technique in use for finite automata).
Another is randomization, which consists of letting all choices be determined by a random number generator. The result is called a probabilistic deterministic algorithm.

Examples

Example 1: Spanning tree computation

The input is an undirected connected graph. An undirected graph is a set of nodes that may or may not be pairwise connected with edges. A subgraph of a graph consists of a subset of its nodes and/or edges. A graph connects two nodes if we can walk over its edges from one to the other. A path in a graph is a minimal subgraph connecting two of its nodes.
A graph is connected if it connects all of its nodes.
The algorithm: while an edge can be removed such that the graph is still connected, remove such an edge.
The output: a spanning tree, that is, a minimal tree connecting all the nodes.
The result is never uniquely defined (unless the input was a tree already), but always has the same number of edges.

Example 2: Primality testing

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.
It is also clear that if the non-deterministic "computer" branches into many different "computers," each taking one possible path(testing every prime,) then every possible prime divisor will be found. A "computer" here can be a Non-deterministic Turing machine.

See also

★ Non-deterministic Turing machine

★ Nondeterministic finite state machine