Nondeterministic algorithm: Difference between revisions

Content deleted Content added

Inline

Revision as of 06:23, 7 July 2024

In computer science and computer programming, a nondeterministic algorithm is an algorithm that, even for the same input, can exhibit different behaviors on different runs, as opposed to a deterministic algorithm.

Different models of computation give rise to different reasons that an algorithm may be non-deterministic, and different ways to evaluate its performance or correctness:

A concurrent algorithm can perform differently on different runs due to a race condition. This can happen even with a single-threaded algorithm when it interacts with resources external to it. In general, such an algorithm is considered to perform correctly only when all possible runs produce the desired results.
A probabilistic algorithm's behavior depends on a random number generator called by the algorithm. These are subdivided into Las Vegas algorithm, where (like concurrent algorithms) all runs must produce correct output, and Monte Carlo algorithms which are allowed to fail or produce incorrect results with low probability. The performance of such an algorithm is often measured probabilistically, for instance using an analysis of its expected time.
In computational complexity theory, nondeterminism is often modeled using an explicit mechanism for making a nondeterministic choice, such as in a nondeterministic Turing machine. For these models, a nondeterministic algorithm is considered to perform correctly when there exists a sequence of nondeterministic choices that it could make that lead it to a correct result, even when most or all other choice produce incorrect results. This existential power makes nondeterministic algorithms of this sort more efficient than known deterministic algorithms for many problems. The P versus NP problem encapsulates this conjectured greater efficiency available to nondeterministic algorithms. Algorithms of this sort are used to define complexity classes based on nondeterministic time and nondeterministic space complexity. They may be simulated using nondeterministic programming, a method for specifying nondeterministic algorithms and searching for the choices that lead to a correct run, often using a backtracking search.

The notion of nondeterminism was introduced by Robert W. Floyd in 1967.^[1]

References

^ Robert W.Floyd (October 1967). "Nondeterministic Algorithms". Journal of the ACM. 14 (4): 636–644. doi:10.1145/321420.321422. S2CID 1990464.

@@ Line 1: / Line 1: @@
 {{short description|Algorithm whose behavior and output may depend on the run}}
+In [[computer science]] and [[computer programming]], a '''nondeterministic algorithm''' is an [[algorithm]] that, even for the same input, can exhibit different behaviors on different runs, as opposed to a [[deterministic algorithm]].
-{{about|nondeterminism in [[computer programming]]|nondeterminism in [[computational complexity theory]]|Nondeterministic model of computation}}
-{{Confusing|reason=the word "nondeterministic" is used with two different meanings|talk=Talk:Nondeterministic algorithm#Misleading Article|date=January 2022}}
+Different [[model of computation|models of computation]] give rise to different reasons that an algorithm may be non-deterministic, and different ways to evaluate its performance or correctness:
-In [[computer programming]], a '''nondeterministic algorithm''' is an [[algorithm]] that, even for the same input, 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 [[probabilistic 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. The nondeterministic algorithms are often used to find an approximation to a solution, when the exact solution would be too costly to obtain using a deterministic one.
+*A [[concurrent algorithm]] can perform differently on different runs due to a [[race condition]]. This can happen even with a single-threaded algorithm when it interacts with resources external to it. In general, such an algorithm is considered to perform correctly only when ''all'' possible runs produce the desired results.
+*A [[probabilistic algorithm]]'s behavior depends on a [[random number generator]] called by the algorithm. These are subdivided into [[Las Vegas algorithm]], where (like concurrent algorithms) all runs must produce correct output, and [[Monte Carlo algorithm]]s which are allowed to fail or produce incorrect results with low probability. The performance of such an algorithm is often measured probabilistically, for instance using an analysis of its [[expected time]].
+*In [[computational complexity theory]], nondeterminism is often modeled using an explicit mechanism for making a nondeterministic choice, such as in a [[nondeterministic Turing machine]]. For these models, a nondeterministic algorithm is considered to perform correctly when ''there exists'' a sequence of nondeterministic choices that it could make that lead it to a correct result, even when most or all other choice produce incorrect results. This existential power makes nondeterministic algorithms of this sort more efficient than known deterministic algorithms for many problems. The [[P versus NP problem]] encapsulates this conjectured greater efficiency available to nondeterministic algorithms. Algorithms of this sort are used to define [[complexity class]]es based on [[nondeterministic time]] and [[nondeterministic space]] complexity. They may be simulated using [[nondeterministic programming]], a method for specifying nondeterministic algorithms and searching for the choices that lead to a correct run, often using a [[backtracking search]].
-The notion was introduced by [[Robert W. Floyd]] in 1967.<ref>
+The notion of nondeterminism was introduced by [[Robert W. Floyd]] in 1967.<ref>
 {{cite journal
 | title = Nondeterministic Algorithms
@@ Line 18: / Line 20: @@
 | doi-access = free
 }}</ref>
-==Use==
-Often in [[computational theory]], the term "algorithm" refers to a [[deterministic algorithm]]. 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 automaton]]. In some scenarios, all possible paths are allowed to run simultaneously.
-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 person walking down a path in a forest and, every time they step further, they must pick which fork in the road they wish 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 person walking through the forest may only find their cabin if they pick some combination of "correct" paths). The choices can be interpreted as guesses in a [[search algorithm|search]] process.
-A large number of problems can be conceptualized through nondeterministic algorithms, including the most famous unresolved question in computing theory, [[P&nbsp;vs&nbsp;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 construction]] for this technique in use for [[finite automata]]).
-Another is [[Randomized algorithm|randomization]], which consists of letting all choices be determined by a [[random number generator]]. The result is called a [[probabilistic]] deterministic algorithm.
-==See also==
-* [[Nondeterministic Turing machine]]
-* [[Nondeterministic programming]]
 ==References==

Revision as of 06:23, 7 July 2024

References

Further reading