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

Main Site Subjects

Related Subjects

Related Phrases

Related Words