A property of a computation which may have more than one result.
One way to implement a nondeterministic algorithm is using backtracking, another is to explore (all) possible solutions in parallel.
[dih-tur-muh-niz-uh m] /dɪˈtɜr məˌnɪz əm/ noun 1. the doctrine that all facts and events exemplify natural laws. 2. the doctrine that all events, including human choices and decisions, have sufficient causes. /dɪˈtɜːmɪˌnɪzəm/ noun 1. Also called necessitarianism. the philosophical doctrine that all events including human actions and choices are fully determined by preceding events and […]
- Nondeterministic automaton
theory (Or “probabilistic automaton”) An automaton in which there are several possible actions (outputs and next states) at each state of the computation such that the overall course of the computation is not completely determined by the program, the starting state, and the initial inputs. See also nondeterministic Turing Machine. (1996-05-07)
- Nondeterministic polynomial time
complexity (NP) A set or property of computational decision problems solvable by a nondeterministic Turing Machine in a number of steps that is a polynomial function of the size of the input. The word “nondeterministic” suggests a method of generating potential solutions using some form of nondeterminism or “trial and error”. This may take exponential […]
- Nondeterministic turing machine
complexity A normal (deterministic) Turing Machine that has a “guessing head” – a write-only head that writes a guess at a solution on the tape first, based on some arbitrary internal algorithm. The regular Turing Machine then runs and returns “yes” or “no” to indicate whether the solution is correct. A nondeterministic Turing Machine can […]