L, NL & Savitch's Theorem

Log-space classes, NL-complete PATH, and the NL ⊆ L² simulation.

The idea

$\mathrm{L}$ and $\mathrm{NL}$ are the complexity classes of logarithmic space. Space is charged on a separate work tape: the input tape is read-only and free, since the input alone already fills $n$ cells. $\mathrm{L}$ is the class of languages a deterministic Turing machine decides with $O(\log n)$ work cells, and $\mathrm{NL}$ the same for a nondeterministic machine. A logarithmic work tape cannot hold a copy of the input; it holds a constant number of pointers — an index into the input, a counter, the name of a vertex.

The central problem is $\mathrm{PATH}$: given a directed graph $G$ and vertices $s$ and $t$, is there a directed path from $s$ to $t$? A nondeterministic machine decides it with pointers alone: hold the current vertex, guess an out-neighbor, step to it, and count the steps so as to reject after $N$ of them. Every language in $\mathrm{NL}$ log-space reduces to $\mathrm{PATH}$, so $\mathrm{PATH}$ is $\mathrm{NL}$-complete, and $\mathrm{L} = \mathrm{NL}$ if and only if $\mathrm{PATH} \in \mathrm{L}$ — a question that remains open.

Theorem (Savitch's theorem).

For every $s(n) \ge \log n$, a nondeterministic machine using $s(n)$ space can be simulated by a deterministic machine using $O(s(n)^{2})$ space; that is, $\mathrm{NSPACE}(s(n)) \subseteq \mathrm{SPACE}(s(n)^{2})$. In particular $\mathrm{NL} \subseteq \mathrm{DSPACE}(\log^{2} n)$.

Nondeterminism therefore costs at most a squaring of the space. The figure shows one step of the deterministic simulation, which splits a path at a midpoint.

Ways to work on it

• Walkthrough. Log-space classes, NL-complete PATH, and Savitch's recursive reachability.
• Practice. A quantitative fact about log-space classes or Savitch's bound.
• Hardest. Derive Savitch's quadratic space bound and place NL inside L².

Not sure where to start? Take the ten-question placement test.