Nondeterministic Algorithm

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.

Read more about Nondeterministic Algorithm:  Use, Implementing Nondeterministic Algorithms With Deterministic Ones

Other articles related to "nondeterministic algorithm, algorithm":

Nondeterministic Algorithm - Examples - Example 3: Primality Testing
... A nondeterministic algorithm for this problem is the following based on Fermat's little theorem Repeat thirty times Pick a random integer a such that 2 ≤ a ≤ n-1 ... 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 ...