computer science Computer science is the study of computation, information, and automation. Computer science spans Theoretical computer science, theoretical disciplines (such as algorithms, theory of computation, and information theory) to Applied science, ...

and

computer programming Computer programming or coding is the composition of sequences of instructions, called computer program, programs, that computers can follow to perform tasks. It involves designing and implementing algorithms, step-by-step specifications of proc ...

, a nondeterministic algorithm is an

algorithm In mathematics and computer science, an algorithm () is a finite sequence of Rigour#Mathematics, mathematically rigorous instructions, typically used to solve a class of specific Computational problem, problems or to perform a computation. Algo ...

that, even for the same input, can exhibit different behaviors on different runs, as opposed to a deterministic algorithm. Different

models of computation In computer science, and more specifically in computability theory and computational complexity theory, a model of computation is a model which describes how an output of a mathematical function is computed given an input. A model describes how ...

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 A race condition or race hazard is the condition of an electronics, software, or other system where the system's substantive behavior is dependent on the sequence or timing of other uncontrollable events, leading to unexpected or inconsistent ...

. 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 Random number generation is a process by which, often by means of a random number generator (RNG), a sequence of numbers or symbols is generated that cannot be reasonably predicted better than by random chance. This means that the particular ou ...

called by the algorithm. These are subdivided into

Las Vegas algorithm In computing, a Las Vegas algorithm is a randomized algorithm that always gives Correctness (computer science), correct results; that is, it always produces the correct result or it informs about the failure. However, the runtime of a Las Vegas alg ...

s, for which (like concurrent algorithms) all runs must produce correct output, and

Monte Carlo algorithm In computing, a Monte Carlo algorithm is a randomized algorithm whose output may be incorrect with a certain (typically small) probability. Two examples of such algorithms are the Karger–Stein algorithm and the Monte Carlo algorithm for mini ...

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, the average-case complexity of an algorithm is the amount of some computational resource (typically time) used by the algorithm, averaged over all possible inputs. It is frequently contrasted with worst-case com ...

. *In

computational complexity theory In theoretical computer science and mathematics, computational complexity theory focuses on classifying computational problems according to their resource usage, and explores the relationships between these classifications. A computational problem ...

, nondeterminism is often modeled using an explicit mechanism for making a nondeterministic choice, such as in a

nondeterministic Turing machine In theoretical computer science, a nondeterministic Turing machine (NTM) is a theoretical model of computation whose governing rules specify more than one possible action when in some given situations. That is, an NTM's next state is ''not'' comp ...

. 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 The P versus NP problem is a major unsolved problem in theoretical computer science. Informally, it asks whether every problem whose solution can be quickly verified can also be quickly solved. Here, "quickly" means an algorithm exists that ...

encapsulates this conjectured greater efficiency available to nondeterministic algorithms. Algorithms of this sort are used to define

complexity class In computational complexity theory, a complexity class is a set (mathematics), set of computational problems "of related resource-based computational complexity, complexity". The two most commonly analyzed resources are time complexity, time and s ...

es based on nondeterministic time and nondeterministic space complexity. They may be simulated using

nondeterministic programming A nondeterministic programming language is a programming language, language which can specify, at certain points in the Computer program, program (called "choice points"), various alternatives for Control flow, program flow. Unlike an Conditional ...

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

References

Further reading