In computer science, 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.
Contents |
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. This is natural when the problem solved by the algorithm inherently allows multiple outcomes, or when there is a single outcome but there are multiple ways to get there and we simply don't care which of them is chosen. What these cases have in common is that the nondeterministic algorithm always arrives at a valid solution, no matter which choices are made at the choice points encountered underway.
Another use of nondeterministic algorithms is made in computational complexity theory. There, it is customary to define nondeterministic algorithms that do not always arrive at a correct solution, but are guaranteed to arrive at a correct solution if the right choices are made underway. The choices are effectively guesses in a search process. It turns out that a large number of real-life problems can be naturally stated in this way, and the most famous unresolved question in computing theory is about such problems.
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: Shopping list
Consider a shopping list: a list of items to buy.
It can be interpreted in two ways:
- The instruction to buy all of those items, in any order. This is a nondeterministic algorithm.
- The instruction to buy all of those items, in the order given. This is a deterministic algorithm.
Usually, it will be interpreted in the first way.
Example 2: Merge sort
Suppose we have a finite collection of things (say, 300 student exams) that we need to sort (say, by student number).
One algorithm to do this (called merge sort):
- split the collection in two approximately equal parts
- sort the two halves with merge sort (i.e. recursively)
- merge the results
Items can only be uniquely sorted if the sorting criterion chosen always defines a total order; e.g. student numbers are probably unique, but if we sort exams by family name and two students happen to have the same name, the order in which their exams get sorted is left undefined. Merge sort is guaranteed to arrive at any one of the possible valid results.
Example 3: Spanning tree
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 subgraph that is a tree connecting all the nodes.
Every graph (that is connected and not a tree) has multiple spanning trees, so we once again have an example where the problem itself allows multiple possible outcomes, and the algorithm chosen can arrive at any one of them, but will never arrive at something else.
This is, again, an algorithm that always arrives at a correct solution to the problem.
Example 4: Primality testing
The problem: given a natural number, determine whether it is prime.
A nondeterministic algorithm for this problem is the following:
- Pick any integer k such that 2 ≤ k ≤ √(n).
- 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.
This algorithm is as nondeterministic as the previous ones, but its relationship to the stated problem is different: it does not always arrive at a valid solution, but only with certain combinations of choices. This is an example of the search type of nondeterministic algorithm.
See also
This entry is from Wikipedia, the leading user-contributed encyclopedia. It may not have been reviewed by professional editors (see full disclaimer)
