A non-deterministic algorithm is a theoretical computation model in which, at each step, several actions may be available rather than exactly one. The model is defined to accept an input if at least one sequence of choices leads to an accepting outcome — it does not literally compute every branch at once, and it is not a physical machine. This abstraction is the basis of the non-deterministic Turing machine and, in turn, of complexity classes like NP: a problem is in NP if a non-deterministic machine can verify a solution in polynomial time.
Because real computers are deterministic, non-determinism is only approximated in practice — typically with a backtracking search that explores branches one at a time, or with a randomized algorithm that samples among the available choices. Both approaches cost real time and memory; they don't give the free parallelism the theoretical model assumes.
The value of non-determinism is conceptual, not a runtime speedup. Treating "guess a choice, then verify" as a single step lets complexity theory define classes like NP cleanly and lets algorithm designers reason about a problem's structure — e.g., whether a solution is easy to check even if it's hard to find — before committing to a concrete search strategy.
Simulating non-determinism with backtracking or randomization can make some search and optimization problems (such as constraint satisfaction, route planning, or scheduling) tractable to attempt, since it provides a systematic way to explore multiple candidate paths. The trade-off is added implementation complexity: the simulation must track or reconstruct branches, and for problems with a large or exponential number of possible paths, the search can still take prohibitively long, since no shortcut around the underlying complexity is created by the abstraction itself.
More terms
Glossary term
Glossary term
Collaborate with your team on reliable Generative AI features.
Want expert guidance? Book a 1:1 onboarding session from your dashboard.