# Nondeterministic algorithm

Talk0*34,141*pages on

this wiki

Assessment |
Biopsychology |
Comparative |
Cognitive |
Developmental |
Language |
Individual differences |
Personality |
Philosophy |
Social |

Methods |
Statistics |
Clinical |
Educational |
Industrial |
Professional items |
World psychology |

**Statistics:**
Scientific method ·
Research methods ·
Experimental design ·
Undergraduate statistics courses ·
Statistical tests ·
Game theory ·
Decision theory

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.

- 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). |