$L$ versus $NL$

This is the space-bounded analogue of $P$ versus $NP$: does nondeterminism add power for Turing machines restricted to $O(\log n)$ work space? Here $L$ and $NL$ denote deterministic and nondeterministic logarithmic space, with a read-only input tape. The question took its modern shape around 1970, when Savitch first related the two measures; no unique first proposal is documented [Savitch1970].

The canonical complete problem is reachability: deciding whether a directed graph contains a path from $s$ to $t$ is $NL$-complete, so $L=NL$ if and only if this single problem lies in deterministic logspace. Savitch's theorem gives $NL\subseteq\operatorname{SPACE}(\log^2 n)$, simulating nondeterminism at the cost of squaring the space bound [Savitch1970]. In the other direction, the Immerman–Szelepcsényi theorem established the surprising equality $NL=coNL$, showing that nondeterministic logarithmic space, unlike (conjecturally) nondeterministic polynomial time, is closed under complement [Immerman1988].

Neither result collapses $NL$ to $L$, and the problem is open: a resolution requires either a deterministic $O(\log n)$-space algorithm for directed reachability or a proof that none exists [AroraBarak2009].