Nondeterministic algorithm
Encyclopedia
In computer science
, a nondeterministic algorithm is an algorithm
that can exhibit different behaviors on different runs, as opposed to a deterministic algorithm
. There are several ways an algorithm may behave differently from run to run. A concurrent algorithm can perform differently on different runs due to a race condition
. A probabalistic algorithm's behaviors depends on a random number generator. An algorithm that solves a problem in nondeterministic polynomial time can run in polynomial time or exponential time depending on the choices it makes during execution.
. A nondeterministic algorithm is different from its more familiar deterministic counterpart in its ability to arrive at outcomes using various routes. If a deterministic algorithm represents a single path from an input to an outcome, a nondeterministic algorithm represents a single path stemming into many paths, some of which may arrive at the same output and some of which may arrive at unique outputs. This property is captured mathematically in "nondeterministic" models of computation such as the nondeterministic finite state machine
.
In algorithm design, nondeterministic algorithms are often used when the problem solved by the algorithm inherently allows multiple outcomes (or when there is a single outcome with multiple paths by which the outcome may be discovered, each equally preferable). Crucially, every outcome the nondeterministic algorithm produces is valid, regardless of which choices the algorithm makes while running.
In computational complexity theory
, nondeterministic algorithms are ones that, at every possible step, can allow for multiple continuations (imagine a man walking down a path in a forest and, every time he steps further, he must pick which fork in the road he wishes to take). These algorithms do not arrive at a solution for every possible computational path; however, they are guaranteed to arrive at a correct solution for some path (i.e., the man walking through the forest may only find his cabin if he picks some combination of "correct" paths). The choices can be interpreted as guess
es in a search process.
A large number of problems can be conceptualized through nondeterministic algorithms, including the most famous unresolved question in computing theory, P = NP.
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.
One algorithm to do this (called merge sort
):
Items can only be uniquely sorted if the sorting criterion chosen always defines a total order
; e.g. student numbers are expected to be unique, but if we sort exams by name and two students happen to have the same name, the order in which their exams get sorted is left undefined. In such cases, merge sort will always arrive at one of the possible valid orderings, but which one is left unspecified—hence it is nondeterministic.
. 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.
n larger than two, determine whether it is prime
.
A nondeterministic algorithm for this problem is the following based on Fermat's little theorem
:
If this algorithm returns the answer composite then the number is certainly not prime. If the algorithm returns the answer probably prime then there is a high probability that the number is prime, but a slight chance that it is composite. This is an example of a probabilistic nondeterministic algorithm, because it will not always return the same result given a particular input.
Computer science
Computer science or computing science is the study of the theoretical foundations of information and computation and of practical techniques for their implementation and application in computer systems...
, a nondeterministic algorithm is an algorithm
Algorithm
In mathematics and computer science, an algorithm is an effective method expressed as a finite list of well-defined instructions for calculating a function. Algorithms are used for calculation, data processing, and automated reasoning...
that can exhibit different behaviors on different runs, as opposed to a deterministic algorithm
Deterministic algorithm
In computer science, a deterministic algorithm is an algorithm which, in informal terms, behaves predictably. Given a particular input, it will always produce the same output, and the underlying machine will always pass through the same sequence of states...
. There are several ways an algorithm may behave differently from run to run. A concurrent algorithm can perform differently on different runs due to a race condition
Race condition
A race condition or race hazard is a flaw in an electronic system or process whereby the output or result of the process is unexpectedly and critically dependent on the sequence or timing of other events...
. A probabalistic algorithm's behaviors depends on a random number generator. An algorithm that solves a problem in nondeterministic polynomial time can run in polynomial time or exponential time depending on the choices it makes during execution.
Use
Often in computational theory, the term "algorithm" refers to a deterministic algorithmDeterministic algorithm
In computer science, a deterministic algorithm is an algorithm which, in informal terms, behaves predictably. Given a particular input, it will always produce the same output, and the underlying machine will always pass through the same sequence of states...
. A nondeterministic algorithm is different from its more familiar deterministic counterpart in its ability to arrive at outcomes using various routes. If a deterministic algorithm represents a single path from an input to an outcome, a nondeterministic algorithm represents a single path stemming into many paths, some of which may arrive at the same output and some of which may arrive at unique outputs. This property is captured mathematically in "nondeterministic" models of computation such as the nondeterministic finite state machine
Nondeterministic finite state machine
In the automata theory, a nondeterministic finite state machine or nondeterministic finite automaton is a finite state machine where from each state and a given input symbol the automaton may jump into several possible next states...
.
In algorithm design, nondeterministic algorithms are often used when the problem solved by the algorithm inherently allows multiple outcomes (or when there is a single outcome with multiple paths by which the outcome may be discovered, each equally preferable). Crucially, every outcome the nondeterministic algorithm produces is valid, regardless of which choices the algorithm makes while running.
In computational complexity theory
Computational complexity theory
Computational complexity theory is a branch of the theory of computation in theoretical computer science and mathematics that focuses on classifying computational problems according to their inherent difficulty, and relating those classes to each other...
, nondeterministic algorithms are ones that, at every possible step, can allow for multiple continuations (imagine a man walking down a path in a forest and, every time he steps further, he must pick which fork in the road he wishes to take). These algorithms do not arrive at a solution for every possible computational path; however, they are guaranteed to arrive at a correct solution for some path (i.e., the man walking through the forest may only find his cabin if he picks some combination of "correct" paths). The choices can be interpreted as guess
Guess
The word guess commonly refers to a conjecture or estimation. To "guess" is to make a prediction without sufficient information or knowledge.Guess may also refer to:*Guess , an American name-brand clothing line...
es in a search process.
A large number of problems can be conceptualized through nondeterministic algorithms, including the most famous unresolved question in computing theory, P = NP.
Implementing nondeterministic algorithms with 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 constructionPowerset construction
In the theory of computation and Automata theory, the powerset construction or subset construction is a standard method for converting a nondeterministic finite automaton into a deterministic finite automaton which recognizes the same formal language...
for this technique in use for finite automata).
Another is randomization
Randomized algorithm
A randomized algorithm is an algorithm which employs a degree of randomness as part of its logic. The algorithm typically uses uniformly random bits as an auxiliary input to guide its behavior, in the hope of achieving good performance in the "average case" over all possible choices of random bits...
, which consists of letting all choices be determined by a random number generator. The result is called a probabilistic deterministic algorithm.
Example 1: 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
Merge sort
Merge sort is an O comparison-based sorting algorithm. Most implementations produce a stable sort, meaning that the implementation preserves the input order of equal elements in the sorted output. It is a divide and conquer algorithm...
):
- split the collection in two approximately equal parts
- sort the two halves with merge sort (i.e. recursivelyRecursionRecursion is the process of repeating items in a self-similar way. For instance, when the surfaces of two mirrors are exactly parallel with each other the nested images that occur are a form of infinite recursion. The term has a variety of meanings specific to a variety of disciplines ranging from...
) - merge the results
Items can only be uniquely sorted if the sorting criterion chosen always defines a total order
Total order
In set theory, a total order, linear order, simple order, or ordering is a binary relation on some set X. The relation is transitive, antisymmetric, and total...
; e.g. student numbers are expected to be unique, but if we sort exams by name and two students happen to have the same name, the order in which their exams get sorted is left undefined. In such cases, merge sort will always arrive at one of the possible valid orderings, but which one is left unspecified—hence it is nondeterministic.
Example 2: Spanning tree
The input is an undirected connected graphGraph (mathematics)
In mathematics, a graph is an abstract representation of a set of objects where some pairs of the objects are connected by links. The interconnected objects are represented by mathematical abstractions called vertices, and the links that connect some pairs of vertices are called edges...
. 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
Path (graph theory)
In graph theory, a path in a graph is a sequence of vertices such that from each of its vertices there is an edge to the next vertex in the sequence. A path may be infinite, but a finite path always has a first vertex, called its start vertex, and a last vertex, called its end vertex. Both of them...
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
Spanning tree (mathematics)
In the mathematical field of graph theory, a spanning tree T of a connected, undirected graph G is a tree composed of all the vertices and some of the edges of G. Informally, a spanning tree of G is a selection of edges of G that form a tree spanning every vertex...
, 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 3: Primality testing
The problem: given a natural numberNatural number
In mathematics, the natural numbers are the ordinary whole numbers used for counting and ordering . These purposes are related to the linguistic notions of cardinal and ordinal numbers, respectively...
n larger than two, determine whether it is prime
Prime number
A prime number is a natural number greater than 1 that has no positive divisors other than 1 and itself. A natural number greater than 1 that is not a prime number is called a composite number. For example 5 is prime, as only 1 and 5 divide it, whereas 6 is composite, since it has the divisors 2...
.
A nondeterministic algorithm for this problem is the following based on Fermat's little theorem
Fermat's little theorem
Fermat's little theorem states that if p is a prime number, then for any integer a, a p − a will be evenly divisible by p...
:
- Repeat thirty times:
- Pick a random integer a such that 2 ≤ a ≤ n-1.
- If
, return answer composite
- Return answer probably prime.
If this algorithm returns the answer composite then the number is certainly not prime. If the algorithm returns the answer probably prime then there is a high probability that the number is prime, but a slight chance that it is composite. This is an example of a probabilistic nondeterministic algorithm, because it will not always return the same result given a particular input.
See also
- Non-deterministic Turing machineNon-deterministic Turing machineIn theoretical computer science, a Turing machine is a theoretical machine that is used in thought experiments to examine the abilities and limitations of computers....
- Nondeterministic finite state machineNondeterministic finite state machineIn the automata theory, a nondeterministic finite state machine or nondeterministic finite automaton is a finite state machine where from each state and a given input symbol the automaton may jump into several possible next states...
- Nondeterministic programmingNondeterministic programmingA nondeterministic programming language is a language which can specify, at certain points in the program , various alternatives for program flow...