the class NL

NL is L with one extra superpower: the machine may guess. Picture our memory-starved auditor again, still allowed only a few sticky notes, but now permitted to make lucky guesses about which way to turn at each fork, as long as some sequence of lucky guesses reaches the goal. They do not have to find the right path systematically; they just have to be able to verify a guessed path step by step using only their tiny notebook. NL is the family of problems solvable that way.

Formally, NL equals NSPACE(log n): the languages accepted by a nondeterministic Turing machine using O(log n) work space, where the machine accepts an input if at least one of its guessed computation paths leads to an accept state. The crucial discipline is that each guess must be checkable on the fly within log space, so the machine can hold only a constant number of pointers as it explores. The textbook way to see NL in action is directed graph reachability: to test whether there is a path from s to t, the machine remembers only the current vertex (one pointer, O(log n) bits) and repeatedly guesses the next edge to follow, never storing the path it has taken.

NL sits just above L and just below P: L is contained in NL is contained in P, and all three inclusions are believed strict but none is proved. Two landmark facts make NL special. By Savitch's theorem, NL is contained in SPACE((log n)^2), so this nondeterminism costs only a quadratic squeeze of deterministic space. By the Immerman-Szelepcsenyi theorem, NL equals co-NL: nondeterministic log space is closed under complement, which time-bounded nondeterminism is not known to be. A common misconception is that nondeterminism here means randomness or real parallel hardware; it is neither, just the mathematical 'does some accepting guess exist' device.