Methods | Statistics | Clinical | Educational | Industrial | Professional items | World psychology |
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.
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).
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 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
- 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.
|This page uses Creative Commons Licensed content from Wikipedia (view authors).|