imported>Tpreu: /* History */ Added a paragraph on the history of randomized algorithms.

2025-11-08T18:05:12Z

History: Added a paragraph on the history of randomized algorithms.

New page

{{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]].

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:
*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]]s, for which (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, for each input, ''there exists'' a run that produces the desired result, even when other runs 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]].

==History==

[[Randomized_algorithm#Early_history|Explicit algorithms using randomness]] were considered before formalizing the concept of nondeterminism in computer science.
In 1917, [[Henry Cabourn Pocklington|Henry C. Pocklington]] introduced a randomized algorithm known as [[Pocklington's algorithm]] for efficiently finding [[square root]]s modulo prime numbers.<ref>{{citation |last1=Williams |first1=H. C. |title=Mathematics of Computation 1943–1993: a half-century of computational mathematics; Papers from the Symposium on Numerical Analysis and the Minisymposium on Computational Number Theory held in Vancouver, British Columbia, August 9–13, 1993 |volume=48 |pages=481–531 |year=1994 |editor-last=Gautschi |editor-first=Walter |series=Proceedings of Symposia in Applied Mathematics |contribution=Factoring integers before computers |publisher=Amer. Math. Soc., Providence, RI |doi=10.1090/psapm/048/1314885 |mr=1314885 |last2=Shallit |first2=J. O. |isbn=978-0-8218-0291-5 |author1-link=Hugh C. Williams |author2-link=Jeffrey Shallit}}; see p. 504, "Perhaps Pocklington also deserves credit as the inventor of the randomized algorithm".</ref>
In the 1930s, [[Enrico Fermi]] experimented with the [[Monte Carlo method]] while studying neutron diffusion, but he did not publish this work.<ref>{{cite journal |last = Metropolis |first = N. |author-link = Nicholas Metropolis |url = http://library.lanl.gov/cgi-bin/getfile?15-12.pdf |title = The beginning of the Monte Carlo method |journal = Los Alamos Science |issue = 1987 Special Issue dedicated to Stanislaw Ulam |pages = 125–130 |year = 1987 }}</ref>
[[Monte_Carlo_method#History|Scientists at the Los Alamos National Laboratory]] in the 1940s and 50s developed and implemented the concept leading to the first publications concerned with Monte Carlo algorithms.<ref>{{cite journal |last1 = Metropolis |first1 = N. |author1-link = Nicholas Metropolis |last2 = Ulam |first2 = S. |author-link2=Stanislaw Ulam |year=1949 |title = The Monte Carlo Method |journal = Journal of the American Statistical Association |volume=44 |issue=247 |pages=335–341 |doi = 10.1080/01621459.1949.10483310 |pmid=18139350 |jstor=2280232 }}</ref><ref>{{cite journal |last1 = Metropolis |first1 = N. |author1-link = Nicholas Metropolis |last2=Rosenbluth |first2=Arianna W.|last3=Rosenbluth |first3=Marshall N. |last4=Teller |first4=Augusta H. |last5=Teller |first5=Edward |year=1953 |title=Equation of State Calculations by Fast Computing Machines |journal=Journal of Chemical Physics |volume=21 |issue=6 |page=1087 |doi = 10.1063/1.1699114 |bibcode = 1953JChPh..21.1087M |title-link = Equation of State Calculations by Fast Computing Machines |osti = 4390578 |s2cid = 1046577 }}</ref>

[[Michael O. Rabin]] and [[Dana Scott]] introduced and formalized [[Nondeterministic finite automaton|nondeterministic finite automatons]] (NFA) in 1959.<ref>{{cite journal |doi=10.1147/rd.32.0114 |last1=Rabin |first1=M. O. |last2=Scott |first2=D. |title=Finite Automata and Their Decision Problems |journal=IBM Journal of Research and Development |volume=3 |issue=2 |pages=114–125 |date=April 1959 }}</ref> In that paper they show the equivalence to [[Deterministic finite automaton|deterministic finite automatons]] (DFA) in terms of the ability to recognize languages. They also apply them to [[Turing machine|Turing machines]] (TM) thereby introducing [[Nondeterministic Turing machine|nondeterministic Turing machines]] (NTM). Using NFAs they could reprove in a more streamlined way certain closure properties of [[regular language|regular languages]] previously established by [[Stephen C. Kleene]] and others.

The term ''nondeterministic algorithm'' was used by [[Robert W. Floyd]] as early as 1967.<ref>
{{cite journal
| title = Nondeterministic Algorithms
| author = Robert W.Floyd
| journal = [[Journal of the ACM]]
| volume = 14
| number = 4
|date=October 1967
| pages = 636–644
| doi = 10.1145/321420.321422
| s2cid = 1990464
| doi-access = free
}}</ref>
The paper uses the graphical language of [[flow chart|flow charts]] which is a different way to formalize algorithms compared to automata or Turing machines and at that time was closer to the practice of programming on electronic computers.

In [[philosophy]] ideas revolving around [[Determinism#History|determinism]] vs. [[Free_will#History_of_free_will|free will]] go back at least to ancient Greece. It is worth noting that nondeterminacy as a concept in computer science refers to a rather limited choice between previously explicitly defined, often only finitely many options in each computational step, while in philosophy the possible options do not necessarily have to be laid out or formally defined beforehand. In particular because of this additional property nondeterminism in computer science constitutes a new development compared to nondeterminism in traditional philosophy.

==References==
{{reflist}}

==Further reading==
*{{cite book | title = Introduction to Algorithms |edition=3rd | author = Cormen, Thomas H. |year=2009 |publisher=MIT Press | isbn = 978-0-262-03384-8}}
*{{cite web | url = http://xlinux.nist.gov/dads/HTML/nondetermAlgo.html | title = Nondeterministic algorithm | publisher = National Institute of Standards and Technology |access-date=July 7, 2013}}
*{{cite web | url = http://cs.nyu.edu/courses/spring03/G22.2560-001/nondet.html | title = Non-deterministic Algorithms |publisher=New York University Computer Science |access-date=July 7, 2013}}

{{DEFAULTSORT:Nondeterministic Algorithm}}
[[Category:Computational complexity theory]]
[[Category:Theory of computation]]

Nondeterministic algorithm - Revision history

imported>Tpreu: /* History */ Added a paragraph on the history of randomized algorithms.