Past exam of the mathematics course of the University of Cambridge / 2024 / iii / Paper 124 / 2

A decision problem $B$ is NL-complete when $B\in \mathbf{NL}$ and every language $A\in \mathbf{NL}$ has a deterministic logarithmic space many-one reduction to $B$.

The directed graph reachability problem is the standard example. It lies in NL because a machine stores the current vertex and a counter, nondeterministically guesses at most $|V|-1$ successive edges, and accepts upon reaching $t$; this uses $O(\log |V|)$ space. For hardness, given an NL machine $M$ and input $x$, construct its configuration graph. Its configurations have logarithmic length, adjacency can be computed in logarithmic space, andAdding one target joined from every accepting configuration gives the required logarithmic-space reduction.

It suffices to recognize non-reachability in NL, since directed reachability is NL-complete. Let $c_k$ be the number of vertices reachable from $s$ by a directed path of length at most $k$. Clearly $c_0=1$. The inductive counting argument computes and verifies $c_{k+1}$ from $c_k$ using logarithmic space.

For each vertex $v$, reachability within $k+1$ steps has an NL certificate: guess such a path. Non-reachability within $k+1$ steps can be certified relative to the trusted value $c_k$ by enumerating vertices $u$, exhibiting paths of length at most $k$ to exactly $c_k$ distinct vertices, and checking that none is $v$ or has an edge to $v$. Because there are exactly $c_k$ reachable vertices, this list cannot omit a reachable predecessor. Counters, vertex names and one guessed path need only logarithmic space. Repeating this check in a fixed vertex order and counting the positive cases produces the exact $c_{k+1}$.

After $|V|-1$ rounds, the procedure knows the number of all vertices reachable from $s$. It accepts non-reachability of $t$ after certifying, by the same complete enumeration, that $t$ is absent. Thus the complement of directed reachability belongs to NL. Since every NL language reduces to reachability and log-space reductions are closed under complementation, this proves the Immerman–Szelepcsényi theorem

Membership follows from $\mathbf{NL}=\mathbf{co}\text{-}\mathbf{NL}$. A directed graph is not strongly connected exactly when there is a pair $(u,v)$ for which $v$ is not reachable from $u$. Guessing the pair and using the NL procedure for non-reachability puts non-strong-connectivity in NL, hence strong connectivity is in co-NL and therefore in NL.

For NL-hardness, reduce directed reachability. Given $(G,s,t)$, form $G^{\prime }$ by retaining all edges of $G$, adding $v\to s$ for every vertex $v$, and adding $t\to v$ for every vertex $v$. If $t$ is reachable from $s$ in $G$, then any $u$ reaches any $v$ in $G^{\prime }$ alongConversely, if $G^{\prime }$ is strongly connected then $s$ reaches $t$. A simple $s$-to-$t$ path cannot use an added edge out of $t$ before arriving at $t$, and every added edge into $s$ merely returns the path to its starting vertex; deleting the resulting cycle leaves an $s$-to-$t$ path made from edges of $G$. The construction is computable in logarithmic space, so deciding strong connectivity is