Log Space: L, NL, and Reachability

A tiny scratchpad beside a huge book

On the previous rung you learned to measure memory the way you once measured time: count not the steps a machine takes but the work-tape cells it writes on. The crucial trick was the read-only-input and work-tape convention. Without it, an honest count of space would always be at least n, the length of the input, because the machine has to store the input somewhere. So we split the Turing machine's notebook in two: a read-only input tape the machine may scan as often as it likes but never write on, and a separate, blank work tape whose cells we actually charge for. Now space below n becomes meaningful — and even space far below n.

How little is interesting? The answer is the surprisingly powerful regime of logarithmic space: a work tape of only O(log n) cells. That sounds almost insulting — log n is a sliver, far too small to copy the input. But here is the magic. A number that names a position inside an input of length n needs only about log n bits to write down (think of it as the number of digits you need to count up to n). So O(log n) cells is exactly enough to hold a fixed handful of pointers into the input plus a few small counters. You cannot remember what the input said; you can remember where you are looking and count a little. That is the whole budget, and it is enough to do astonishing things.

L and NL: the two log-space classes

Two classes live at this budget, and the split is the same deterministic-versus-nondeterministic fork you met first with finite automata. L (sometimes written LOGSPACE) is the set of problems a deterministic Turing machine can decide using O(log n) work-tape cells. NL is the same with a nondeterministic machine: it may, at each step, guess-and-verify — branching every which way and accepting if any branch accepts — while still writing only O(log n) cells on its work tape. The nondeterminism is the very same mathematical device, not a random or physical machine you met with the NFA; here it is constrained not in time but in memory.

Here is a clean example of a problem in L. Suppose the input is a string and we want to decide whether it has an even number of a-symbols — the very task you once handed to a tiny DFA. A log-space machine does it with one bit of work tape (a parity flag) and one pointer that sweeps left to right: read the next symbol, flip the flag if it is an a, advance the pointer, accept at the end if the flag reads even. The pointer fits in log n bits, the flag in one bit, and the input is never copied. More striking: deciding whether a number written in binary is divisible by 3 is in L too — you sweep the digits keeping only the running remainder mod 3, which is one of three values, a constant.

Why care about so cramped a class? Two honest reasons. First, log space is the natural home of computations you can run with almost no working memory no matter how vast the data — exactly the situation of a streaming sensor, a router glancing at a packet, or a query against a database far larger than RAM. Second, and deeper: because the space budget is so tight, the relationships between L, NL, and the time classes above them are unusually clean to reason about, and a few of them — unlike the maddening P versus NP — have actually been proved. Log space is where complexity theory gets to win some arguments outright.

Reachability: the heart of NL

There is one problem that is NL, in the sense that everything else in NL is a costume worn over it. It is almost embarrassingly simple to state. Reachability (also called PATH or s-t-connectivity): given a directed graph and two vertices s and t, is there a path from s to t? Picture a maze drawn as dots and one-way arrows; you stand at s and want to know if t is reachable by following arrows. That is the whole question.

Why is reachability in NL, and why does it refuse to fit in our log-space budget any easier way? The obvious algorithm — breadth-first search — needs to remember which vertices it has already visited, a list that can be as long as the whole graph, blowing the log-space budget wide open. The nondeterministic machine sidesteps this with a beautifully frugal trick: rather than map out a path, it guesses one step at a time and never writes the path down. It keeps only two things on its work tape: the name of the vertex it is currently standing on, and a step-counter. At each move it guesses a neighbour, walks there, and increments the counter. If it reaches t, accept. If the counter exceeds the number of vertices without arriving, this branch gives up.

REACHABILITY by a log-space NONDETERMINISTIC machine
  (work tape holds only:  cur = current vertex ,  steps = a counter)

  graph:   s -> a -> b -> t        ( the lucky branch )
           s -> c   (dead end)

  cur := s ;  steps := 0
  repeat:
     guess a neighbour v of cur          <- nondeterministic choice
     cur := v ;  steps := steps + 1
     if cur = t      -> ACCEPT
     if steps > |V|  -> this branch gives up

  one accepting branch:  s -> a -> b -> t   (4 steps, then ACCEPT)

  work tape ever used:  one vertex name + one counter
                        each is about log n bits.  NEVER the path.

The whole path s -> a -> b -> t is never stored — the machine remembers only where it stands now and how many steps it has taken. Both fit in O(log n) cells. Some branch guesses the right next step every time; if a path exists, that lucky branch accepts.

Read that trick carefully, because it is exactly where nondeterminism earns its keep. The machine never holds the visited-set or the path — both too big. It holds one vertex and one counter, and it trusts the branching to find the right next hop. If a path exists, some branch makes all the right guesses and accepts; if none exists, every branch eventually runs the counter out and rejects. This is the guess-and-verify pattern from the NFA, now squeezed to fit a log-space scratchpad. Whether a deterministic log-space machine can match it — whether reachability is in L — is a famous open problem, the L-versus-NL question.

NL-completeness and the log-space translator

Reachability is not merely in NL — it is NL-complete, the very hardest problem in the class, the single puzzle into which every other NL problem can be translated. The notion of "hardest" rides on a reduction, just as it did for NP-completeness — but with one mandatory tightening. We may not use a polynomial-time reduction here, because a polynomial-time translator could itself use up to polynomial space, which would dwarf the whole log-space budget and make the comparison meaningless. So the correct tool is a log-space reduction: a translator that rewrites instances using only O(log n) work-tape cells of its own.

Why is reachability the universal target? Because the very act of running an NL machine is itself a reachability question. Lay out the machine's configuration graph: one vertex for each possible configuration (its state, its head positions, and the O(log n) bits on its work tape), and an arrow from one configuration to another whenever the machine could step between them. Crucially, because the work tape is only O(log n) cells, the total number of configurations is only polynomial in n — small enough that the graph's vertices can each be named by a log-space pointer. The machine accepts its input exactly when there is a path from the start configuration to an accepting one. Deciding the NL computation is solving reachability on that graph.

Start from any problem A in NL, decided by some nondeterministic log-space machine M.
Given an input w, build (in log space) the configuration graph of M running on w: its vertices are M's configurations, named by short pointers because there are only polynomially many.
Add an arrow C -> C' exactly when M could move from configuration C to C' in one step — a check the translator performs locally, reading w (read-only) and a couple of pointers.
Set s = the start configuration and t = the (single, by convention) accepting configuration.
Then 'w is a yes-instance of A' becomes exactly 'there is a path from s to t' — A has been translated into reachability, using only log space. Hence reachability is NL-hard, and being itself in NL, it is NL-complete.

Where log space sits, and two surprises ahead

Now we can place these classes on the larger map. Plainly L is inside NL — a deterministic machine is just a nondeterministic one that never branches. And NL sits inside P: to decide an NL problem deterministically in polynomial time, simply build that polynomial-size configuration graph and run an ordinary reachability search on it, which is fast in time even though it overspends on space. Stacking these gives the chain L is a subset of NL is a subset of P, which itself feeds into the grand sequence you will complete in the final guide: L inside NL inside P inside NP inside PSPACE inside EXPTIME.

Be honest about which links in that chain are known. Whether L equals NL is open — nobody knows if reachability can be decided deterministically in log space. Whether NL equals P is open too. As with P versus NP, these are conjectures, widely believed but unproven; the inclusions are certain, the strictness of the inclusions is not. Resist the easy slip of treating any of these as settled.

Two genuinely proved surprises about NL are waiting in the next guides, and reachability is the lever for both. Savitch's theorem shows the nondeterminism in reachability is not as expensive as it looks: a deterministic machine can solve it in only O((log n)^2) space — squaring the budget, not exploding it. That tame cost is what later forces PSPACE to equal nondeterministic PSPACE. And the Immerman-Szelepcsenyi theorem proves the still more shocking fact that NL equals co-NL: a log-space nondeterministic machine can certify a no-answer to reachability — that t is unreachable — which seemed impossible, since the guess-a-path trick only ever proves a yes. Both results say something deep: at log space, nondeterminism is far weaker, relative to determinism, than the open P-versus-NP gap might lead you to fear.