# Nondeterministic algorithm

(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
34,196pages on
this wiki

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.

## Use Edit

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 Edit

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 Edit

### Example 1: Spanning tree computation Edit

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 Edit

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 ≤ kn-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.