L and NL

A Turing machine is said to run in space s(n) if, on inputs of length n, it never uses more than s(n) cells of work-tape memory. The class L (also written LOGSPACE) consists of all languages decidable by a deterministic Turing machine using O(log n) space; NL is the same but for nondeterministic machines, where acceptance means some computation path accepts within the space bound. The logarithm is not arbitrary — it is precisely the amount of space needed to write down a single pointer (an index or address) into an input of length n, since ⌈log₂ n⌉ bits suffice to name any position among n. A crucial technical convention makes these definitions meaningful: the machine has a read-only input tape and a separate read/write work tape, and only the work tape counts toward the space bound. Without this separation, a machine "using O(log n) space" could never even read its entire input, since scanning n symbols would require the head to move across n positions — but crucially, moving a read head does not require storing the input, only an index into it, and that index fits in O(log n) bits on the work tape. This convention is what allows L and NL to be non-trivial classes containing problems like graph reachability, parity, and regular language membership, rather than being trivially empty. The nondeterministic class NL is best understood through the lens of certificates, but with a twist compared to NP. In NP, a certificate is written down all at once and verified in polynomial time using polynomial space to hold it. In NL, the certificate — such as a path through a graph — is far too large to store in log space, so the machine must instead verify it incrementally, forgetting each piece as soon as it moves past it, retaining only a small log-space "state" (like the current vertex). This distinction between storing a certificate and streaming through one without remembering it is the conceptual heart of nondeterministic space complexity, and it is exactly what makes the completeness structure and the NL = coNL theorem both surprising and provable.

The canonical problem for NL is PATH (sometimes called STCONN or REACHABILITY): > Given a directed graph G and two vertices s and t, does there exist a directed path from s to t?

PATH is in NL. The algorithm guesses the path one vertex at a time, using only enough memory to remember the current vertex, the target, and a step counter bounded by n (the number of vertices) — all representable in O(log n) bits. ``` Algorithm: NL-PATH(G, s, t) // G given as adjacency list/matrix on read-only input tape // work tape holds only: current vertex v, counter i, target t v := s i := 0 while true: if v == t: ACCEPT if i >= n: REJECT // no simple path can exceed n-1 edges nondeterministically choose an edge (v, u) in G if no such edge exists: REJECT v := u i := i + 1 ``` Each of v, i, and t is an integer at most n, so each needs O(log n) bits; the total work-tape usage is O(log n), independent of how large the graph's description is. The machine accepts G, s, t if some sequence of nondeterministic choices reaches ACCEPT — exactly matching the semantics of NL.

Why bounding steps by n suffices: if t is reachable from s at all, it is reachable via a simple path (no repeated vertices), because any cycle in a walk can be excised without breaking connectivity. A simple path has at most n − 1 edges, so capping the counter at n prevents infinite loops while never causing us to miss a real path.

PATH is NL-hard, meaning every language in NL log-space-reduces to PATH. This is proved via the configuration graph of an NL machine M on input x. Each configuration (state, work-tape contents, head positions) is a vertex; since the work tape has O(log n) cells over a fixed alphabet, there are at most 2^(O(log n)) = poly(n) configurations. Draw an edge from configuration C₁ to C₂ if M can move from C₁ to C₂ in one nondeterministic step. Then M accepts x if and only if there is a path from the start configuration to some accepting configuration in this graph — which we can arrange to be a single designated accept vertex by convention. Crucially, this reduction is computable in log space itself: to output the configuration graph edge-by-edge, we only need to track a bounded amount of local information (the current configuration and a candidate successor), each of size O(log n). ``` Reduction: NL-language L via machine M ⟶ instance of PATH Input: x (length n) Build graph G_M,x: vertices = all configurations of M on x // poly(n) many, O(log n) bits each edges (C, C') whenever M transitions C -> C' on some nondeterministic choice s = start configuration t = designated unique accepting configuration Output (G_M,x, s, t) ``` Since PATH is both in NL and NL-hard under log-space reductions, PATH is NL-complete. This makes it the standard tool for proving other problems NL-complete (e.g., 2-satisfiability of certain restricted forms, some formulations of undirected reachability historically, and various graph problems), by reducing PATH to them or reducing them to PATH.

Savitch's theorem, established for the general space hierarchy, applies directly here: any nondeterministic machine using space s(n) ≥ log n can be simulated deterministically in space O(s(n)²). Applied to NL (s(n) = log n), this gives:

Savitch's algorithm for PATH is a divide-and-conquer reachability test: define REACH(u, v, k) to be true iff v is reachable from u in at most 2^k steps, and observe

The recursion depth is O(log n) (since k ranges up to log n), and each level reuses the same O(log n) bits of space for the "middle vertex" w, giving total space O(log² n) — this is the mechanism inherited directly from Savitch's theorem, and it upper-bounds NL without resolving whether NL = L.

Space bound derivation for NL-PATH. The algorithm above stores three quantities: the current vertex v ∈ {1,...,n}, the counter i ∈ {0,...,n}, and (implicitly, fixed) the target t. Each requires ⌈log₂(n+1)⌉ bits, so total work-tape usage is Θ(log n), independent of the number of edges m, which can be as large as n² but lives on the read-only input tape and is never copied. This is why the convention of separating input and work tapes is not a technicality but the entire reason PATH belongs to a sublinear-space class at all.

Correctness of NL-PATH (soundness and completeness of the certificate).

• If t is reachable from s, there exists a simple path s = v₀, v₁, ..., v_k = t with k ≤ n − 1. The nondeterministic branch that guesses exactly this sequence of edges causes the algorithm to reach v = t within i ≤ n − 1 ≤ n steps, hitting the ACCEPT branch. Hence some computation path accepts, so the NL machine accepts (by definition of nondeterministic acceptance: there exists an accepting path).
• If t is not reachable from s, then no matter which edges are chosen, v can never equal t, since v only ever takes values reachable from s (an easy induction on the number of steps: v₀ = s is reachable from s trivially, and if v_i is reachable from s then any out-neighbor v_{i+1} is too). Hence every computation path either loops until i = n and rejects, or gets stuck with no outgoing edge and rejects. No accepting path exists, so the machine correctly rejects.

Time complexity. Although we emphasize space, it is worth noting NL ⊆ P: a machine using O(log n) space has at most 2^O(log n) = poly(n) distinct configurations, so a deterministic simulation exploring the configuration graph via BFS/DFS (which is itself a P-time reachability computation) decides the language in polynomial time. This gives the containment chain

and combined with Savitch, NL ⊆ SPACE(log² n) ⊆ PSPACE as well. Whether any of these containments is strict (except PSPACE ⊊ EXPSPACE, known from the space hierarchy theorem) remains open — in particular L = NL? is unresolved, making PATH one of the most important "boundary" problems in complexity theory, alongside its cousin undirected s-t connectivity (proven to be in L by Reingold's algorithm, a landmark result building on but distinct from the tools here).

The Immerman–Szelepcsényi theorem: NL = coNL

The complement of PATH — call it NON-PATH — asks whether t is not reachable from s. Naively, verifying non-reachability seems to require checking that no path works, which looks like it needs a universal (coNL-style) quantifier over exponentially many candidate paths, with no obvious short certificate. Immerman and Szelepcsényi independently discovered (1987) that this intuition is wrong: coNL = NL, so non-reachability also has a nondeterministic log-space verification. The key technical tool is inductive counting: an NL machine can compute, and certify, the exact number of vertices reachable from s, using only log space, even though it can never write down the set of reachable vertices (that would take Ω(n) bits in general). Let $R_i$ denote the number of vertices reachable from s within i steps ($R_0 = 1$, counting s itself). The crucial recursive fact is:

Given $R_i$ (a single O(log n)-bit number) as already known and certified, the machine can verify, for each candidate vertex v in turn, whether v is reachable within i+1 steps — and simultaneously verify that it has considered every reachable-within-i vertex u (so that it does not undercount), by checking that it has found exactly $R_i$ distinct reachable vertices among the u's it examined. This self-checking mechanism is what lets nondeterminism certify a count rather than a single witness. ``` Algorithm: COUNT-REACHABLE(G, s) // computes R = number of vertices reachable from s, using O(log n) space R := 1 // s itself for i := 1 to n-1: R' := 0 for each vertex v in 1..n: found := FALSE count_u := 0 // counts u's certified reachable within i-1 steps for each vertex u in 1..n: guess whether u is reachable within i-1 steps if guessed "yes": // verify this guess using the (already certified) value R nondeterministically verify u reachable within i-1 steps // (recursively, using the same style of certificate, or // by re-deriving reachability-within-(i-1) certificates) count_u := count_u + 1 if u == v or edge (u, v) exists: found := TRUE if count_u != R: // did we find all reachable-within-(i-1) vertices? REJECT // (this branch is inconsistent; the overall // algorithm only accepts on a consistent branch) if found: R' := R' + 1 R := R' output R ``` Once R (the total number of reachable vertices) is known, testing whether t is reachable, or verifying that it is not reachable, becomes easy in NL: guess and verify, one at a time, R distinct vertices reachable from s (each verification is itself an NL-style guessed path, bounded by the step count), while checking along the way whether t ever appears among them. If exactly R vertices are certified reachable and t is not among them, then t is definitively not reachable — because R is the complete count, missing t cannot be an artifact of an incomplete search. ``` Algorithm: NL-VERIFY-NONREACHABLE(G, s, t) R := COUNT-REACHABLE(G, s) // total number of vertices reachable from s found_t := FALSE distinct_count := 0 for each vertex v in 1..n: guess whether v is reachable from s if guessed "yes": verify v reachable from s // nondeterministic path-guessing, as in NL-PATH distinct_count := distinct_count + 1 if v == t: found_t := TRUE if distinct_count == R and not found_t: ACCEPT // certified: exactly R vertices reachable, t is not one of them else: REJECT ```

Why this stays in log space. Every quantity manipulated — R, R', i, u, v, count_u, distinct_count — is an integer bounded by n, requiring O(log n) bits. The recursive verification of "u reachable within i-1 steps" reuses the same machinery at the previous level; because the algorithm processes levels i = 1, ..., n-1 sequentially and only needs the single number $R_{i-1}$ (not the whole set) to move to level i, the space does not accumulate across levels — it is reused, giving overall O(log n) space rather than O(log n) per level accumulating to more.

Correctness sketch (soundness and completeness of the counting certificate). By induction on i: assume the machine can correctly certify $R_i$ using accepting nondeterministic branches (existence of at least one accepting path that correctly outputs $R_i$, and no accepting path that outputs a wrong value — this "no accepting path errs" property requires care in the actual construction, ensuring that failing an internal consistency check, such as `count_u != R`, always rejects that branch). Given a correct $R_i$, the inductive step correctly computes $R_{i+1}$ because a vertex v is reachable within i+1 steps if and only if it equals s or has an in-neighbor u reachable within i steps — and the algorithm's consistency check (`count_u != R` forces rejection) guarantees that only branches which have truly enumerated all $R_i$ reachable vertices are allowed to contribute to R'; branches that undercount are rejected, and branches cannot overcount because reachability-within-i is itself verified via genuine paths. This gives an NL algorithm for coPATH, hence coNL ⊆ NL. Since NL is closed under complement trivially in the other direction as well (NL-completeness of PATH under log-space reductions, which are closed under complement, means PATH ∈ NL implies coPATH ∈ NL for anything reducing to it), the two containments combine to

More generally, the Immerman–Szelepcsényi technique shows NSPACE(s(n)) = coNSPACE(s(n)) for any space-constructible $s(n) \geq \log n$, a fully general closure-under-complement result for nondeterministic space classes — a symmetry with no known analogue for NTIME (it is a famous open question whether NP = coNP).

Consider the directed graph below with vertices {1, 2, 3, 4, 5}, testing reachability from s = 1 to t = 5.

Running NL-PATH(G, 1, 5): the machine explores nondeterministic branches guessing edges out of the current vertex.

Every branch eventually reaches i = n = 5 without ever landing on v = 5, because vertex 5 has no incoming edges at all in this graph. No accepting branch exists, so NL-PATH correctly rejects: 5 is unreachable from 1.

Now let's certify this rejection using inductive counting, tracing COUNT-REACHABLE(G, 1):

The algorithm computes this sequence step by step. At level i = 2, for example, to confirm $R_2 = 4$ it must nondeterministically re-verify, for each candidate v, whether v has an in-neighbor u known reachable within 1 step (from the certified set of size $R_1 = 3$: vertices {1, 2, 3}), while tallying that it examined exactly 3 such u's before moving on. Vertex 4 gets marked reachable (in-neighbors 2 and 3 are both in the size-3 reachable set), vertex 5 does not (no in-neighbors at all), giving $R_2 = 4$, matching the table. Finally, NL-VERIFY-NONREACHABLE(G, 1, 5) uses $R = R_4 = 4$: it guesses and verifies 4 distinct reachable vertices — {1, 2, 3, 4} — never guessing 5 (any branch that tried to verify 5 as reachable would fail the path-verification subroutine and reject), and since `distinct_count == 4 == R` and `found_t == FALSE`, this branch accepts, correctly certifying that 5 is unreachable from 1 — all within O(log 5) = O(1)-scale (asymptotically O(log n)) work-tape bits per quantity tracked.

The theory of L and NL grew out of foundational work connecting space complexity to structural questions in computation, culminating in a proof that many complexity theorists initially considered surprising enough to double-check carefully.

Logarithmic-space classes are far from a theoretical curiosity; they characterize the resources available to streaming algorithms and embedded systems that process large inputs with tiny working memory, such as network routers scanning packet streams or read-only-memory devices. NL specifically captures the complexity of many graph reachability and pathfinding subroutines that appear as primitives inside compilers (data-flow and dependency analysis), database query optimizers (evaluating transitive-closure-like queries), and model checkers (reachability analysis in finite-state system verification, closely related to questions studied under Measuring Space Complexity). The descriptive-complexity perspective pioneered by Immerman also underlies the theoretical foundations of database query languages: NL corresponds to a natural fragment of logic (transitive closure logic) which directly informs how recursive queries are expressed and optimized in systems supporting features like SQL's recursive common table expressions. The L vs. NL question, and the broader landscape of small-space complexity classes, remains central to understanding the limits of space-efficient computation, feeding directly into open problems addressed by The Space Hierarchy Theorem and into circuit-complexity characterizations of L and NL in terms of bounded-depth, bounded-width circuit families.

Ask the tutor: How exactly does the inductive counting algorithm guarantee that a branch which "undercounts" reachable vertices is always rejected, rather than accidentally accepted?