nondeterminism
/ non-dee-TER-min-iz-um /
A normal (deterministic) algorithm is like following a recipe with no choices: at each step the next move is forced, so the same input always traces the same single path. Nondeterminism is a thought-experiment machine that is allowed, at certain steps, to BRANCH — to try several possibilities at once, as if it could split into parallel copies, or equivalently 'guess' the right choice and only check it later. It is not a real machine you can buy; it is a clean mathematical idealisation that makes definitions like NP crisp.
Two equivalent ways to picture a nondeterministic machine help. (1) Guess-and-check: at the start it magically WRITES DOWN a certificate c (the lucky guess), then runs a perfectly ordinary deterministic verifier on (x, c). We say it ACCEPTS x if there EXISTS some guess that leads to acceptance — one good guess suffices, and bad guesses are simply ignored. (2) Branching tree: whenever a choice arises, the computation forks; the machine accepts if ANY root-to-leaf path accepts. The two views match because the sequence of choices along an accepting path IS the certificate. Crucially, the cost is measured along a SINGLE path: 'nondeterministic polynomial time' means there is an accepting computation of polynomial length, never charging for the exponentially many paths the machine 'could' have explored. That asymmetric acceptance rule — yes if some path says yes — is exactly the existential 'there exists a certificate' in NP's definition.
Why bother with a machine that cannot exist? Because it gives a strikingly simple definition of NP (problems solvable by a polynomial-time nondeterministic machine) that turns out to be exactly equivalent to the down-to-earth verifier/certificate definition. It also pinpoints what P-versus-NP is really asking: can the power to GUESS a solution always be replaced by deterministic work that only costs polynomially more? Two honest cautions: nondeterminism is NOT randomness (a random machine flips fair coins and you care about probabilities; a nondeterministic one accepts if a single lucky path exists, with no probability attached), and it is NOT parallelism you can build, because realising all branches would need exponentially many processors.
Nondeterministic SAT-solving: given a formula with variables x1..xn, the machine 'guesses' a truth assignment in one branching step (each xi true or false), then deterministically evaluates the formula. It accepts iff SOME branch makes the formula true. That single accepting branch is exactly a satisfying assignment — the certificate. The guess hides the hard search; only the cheap check is timed.
Accept if ANY branch accepts; cost is one path's length. The branch taken is the certificate.
Nondeterminism is not randomness and not buildable parallelism. 'It accepts if some path accepts' is a logical existential, not a coin flip; you never pay for the exponentially many other paths. That free guessing is precisely the power P-versus-NP asks whether we can do without.