Margaret Rouse is an award-winning technical writer and teacher known for her ability to explain complex technical subjects simply to a non-technical, business audience. Over…
A non-deterministic 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 non-deterministic algorithm travels in various routes to arrive at the different outcomes.
Non-deterministic algorithms are useful for finding approximate solutions, when an exact solution is difficult or expensive to derive using a deterministic algorithm.
One example of a non-deterministic 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 non-deterministic algorithm can take many paths, with some arriving at the same outputs, and others arriving at different outputs. This feature is mathematically used in non-deterministic computation models like non-deterministic finite automaton.
A non-deterministic algorithm is capable of execution on a deterministic computer which has an unlimited number of parallel processors. A non-deterministic 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 non-deterministic algorithms including the unresolved problem of P vs NP in computing theory.
Non-deterministic algorithms are used in solving problems which allow multiple outcomes. Every outcome the non-deterministic algorithm produces is valid, regardless of the choices made by the algorithm during execution.
Techopedia’s editorial policy is centered on delivering thoroughly researched, accurate, and unbiased content. We uphold strict sourcing standards, and each page undergoes diligent review by our team of top technology experts and seasoned editors. This process ensures the integrity, relevance, and value of our content for our readers.
Margaret is an award-winning technical writer and teacher known for her ability to explain complex technical subjects to a non-technical business audience. Over the past twenty years, her IT definitions have been published by Que in an encyclopedia of technology terms and cited in articles by the New York Times, Time Magazine, USA Today, ZDNet, PC Magazine, and Discovery Magazine. She joined Techopedia in 2011. Margaret's idea of a fun day is helping IT and business professionals learn to speak each other’s highly specialized languages.
What Is Hyperdimensional Computing? Hyperdimensional computing is a new approach to information processing that uses high-dimensional mathematical vectors to represent...
Margaret RouseTechnology Expert
What Does STEM Mean?STEM is an integrated, interdisciplinary, and student-centered approach to learning that encourages critical thinking, creativity, collaboration and...
What Does Distributed Cloud Mean?Distributed cloud is a business model that extends a public cloud provider’s infrastructure and services to...
Trending NewsLatest GuidesReviewsTerm of the Day