Nondeterministic Algorithm

Definition - What does Nondeterministic Algorithm mean?

A nondeterministic algorithm can provide different outputs for the same input on different executions. Unlike a deterministic algorithm which produces only a single output for the same input even on different runs, a nondeterministic algorithm travels in various routes to arrive at the different outcomes. Nondeterministic algorithms are useful for finding approximate solutions, when an exact solution is difficult or expensive to derive using a deterministic algorithm.

Techopedia explains Nondeterministic Algorithm

One example of a nondeterministic algorithm is the execution of concurrent algorithms with race conditions, which can exhibit different outputs on different runs. Unlike a deterministic algorithm which travels a single path from input to output, a nondeterministic algorithm can take many paths, with some arriving at the same outputs, and others arriving at different outputs. This feature is mathematically used in nondeterministic computation models like nondeterministic finite automaton.

A nondeterministic algorithm is capable of execution on a deterministic computer which has an unlimited number of parallel processors. A nondeterministic algorithm usually has two phases and output steps. The first phase is the guessing phase, which makes use of arbitrary characters to run the problem. The second phase is the verifying phase, which returns true or false for the chosen string. There are many problems which can be conceptualized with help of nondeterministic algorithms including the unresolved problem of P vs NP in computing theory. Nondeterministic algorithms are used in solving problems which allow multiple outcomes. Every outcome the nondeterministic algorithm produces is valid, regardless of the choices made by the algorithm during execution.

Share this:

Connect with us

Email Newsletter

Join thousands of others with our weekly newsletter

The 4th Era of IT Infrastructure: Superconverged Systems
The 4th Era of IT Infrastructure: Superconverged Systems:
Learn the benefits and limitations of the 3 generations of IT infrastructure – siloed, converged and hyperconverged – and discover how the 4th...
Approaches and Benefits of Network Virtualization
Approaches and Benefits of Network Virtualization:
Businesses today aspire to achieve a software-defined datacenter (SDDC) to enhance business agility and reduce operational complexity. However, the...
Free E-Book: Public Cloud Guide
Free E-Book: Public Cloud Guide:
This white paper is for leaders of Operations, Engineering, or Infrastructure teams who are creating or executing an IT roadmap.
Free Tool: Virtual Health Monitor
Free Tool: Virtual Health Monitor:
Virtual Health Monitor is a free virtualization monitoring and reporting tool for VMware, Hyper-V, RHEV, and XenServer environments.
Free 30 Day Trial – Turbonomic
Free 30 Day Trial – Turbonomic:
Turbonomic delivers an autonomic platform where virtual and cloud environments self-manage in real-time to assure application performance.