From Wikipedia, the free encyclopedia

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 1 Use 2 Turning nondeterministic algorithms into deterministic ones 3 Examples 3.1 Example 1: Spanning tree computation 3.2 Example 2: Primality testing 4 See also

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.

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.

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.

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.

• Non-deterministic Turing machine
• Nondeterministic finite state machine