L versus NL

Imagine a map with one-way arrows A→B, A→C and B→D. There is a route from A to D through B; choosing C reaches a dead end. The question is whether a fixed, reliable algorithm can answer this kind of route question on every finite directed map while keeping only a few location numbers and counters in working memory. The map itself stays available to read and does not count against that memory budget. Checking one proposed route is easy with so little memory; discovering whether any route exists is the difficulty.[2]

Can a machine explore one-way possibilities while remembering only a few vertex numbers? The writable-memory budget is enough for a fixed number of input positions or counters, while the input remains available to read. This is logarithmic work space. L versus NL asks whether every decision problem solvable with nondeterministic choices under that budget also has a deterministic algorithm under it. Nondeterminism means an accepting computation exists, not that random choices are likely to find it. For an input of $N$ bits, this is $\mathrm L=\mathrm{SPACE}(\log N)$ versus $\mathrm{NL}=\mathrm{NSPACE}(\log N)$, with constant factors allowed and read-only input storage excluded. In an explicitly given directed graph with $n$ vertices, a branch can guess the next vertex, check its arrow from the current vertex by scanning the input, and update a counter. A reachable target has a path with at most $n-1$ arrows after repeated-vertex detours are removed. Keeping only the current vertex, proposed next vertex and counter uses $O(\log n)$ bits. Every branch is stopped after this bound: at least one accepts precisely when the target is reachable. The unknown is a deterministic procedure with that work-space bound for every such input.[2]

More memory already allows a reliable search. The missing guarantee is to handle every directed map using only a fixed number of location numbers and counters, even as the map grows.[2]

Savitch’s theorem gives a deterministic simulation using $O((\log N)^2)$ space, which exceeds the logarithmic target. Undirected connectivity, where each connection can be traveled both ways, has a deterministic logarithmic-space algorithm, but one-way graphs require a separate solution. The 2025 connectivity paper studies conditional hardness and algorithm tradeoffs; its paired alternatives do not provide one unconditional deterministic logarithmic-space algorithm for all directed inputs.[1] [2]

A usual search can keep a record of every location already visited. This problem asks whether that growing record is fundamentally necessary for general one-way reachability. It also represents a much wider class of computations: configurations of a memory-limited machine form another directed map, with allowed computation steps as arrows.[2]

A configuration graph makes the wider significance concrete. Each vertex records one possible machine configuration; an arrow records an allowed next step. For a logarithmic-space computation this graph has only polynomially many configurations, and its arrows can be tested without storing the whole graph. Asking whether an accepting configuration is reachable captures any NL computation. Thus the small route-checking example reflects a general question about whether a successful sequence of choices saves essential memory.[2]