Nondeterministic

The term nondeterministic refers to a model of computation or process in which several possible next steps may be available from a given state, and the choice among those steps is not determined by the input alone. In theoretical contexts, a nondeterministic machine can branch into multiple computation paths, with acceptance defined by the existence of at least one accepting path.

In automata theory, a nondeterministic finite automaton (NFA) can move to several possible next states for a given input symbol, or may take epsilon transitions without consuming input. NFAs differ from deterministic finite automata (DFAs) only in how transitions are chosen; they recognize the same class of regular languages, though NFAs can be more compact. A language is accepted by an NFA if there exists some sequence of choices that leads to an accepting state.

In complexity theory, nondeterministic Turing machines (NTMs) define NP: a language is in NP if an accepting path exists in polynomial time.

Nondeterminism is a theoretical abstraction rather than a physical capability; real devices are deterministic or rely on randomness. In practice, nondeterministic models are often simulated by exploring multiple paths or by constructing equivalent deterministic machines, such as via the subset construction for NFAs or by proof certificates used in NP. NP-complete problems are among the hardest in NP.

In other contexts, nondeterminism describes concurrent or asynchronous systems where a process may take several possible actions, with no single global order guaranteed. The term is sometimes juxtaposed with randomness, but nondeterminism persists as a separate modeling concept.