Show that problem of Shortest-Path in digraph is in NL
The difficulty here is how to check using non-deterministic logarithmic space that there is no path from $s$ to $t$ of some length $\ell$. We cannot just go over all possible paths of length $\ell$ since in order to do this we will need to "remember" $\ell$ vertices, whereas we are only allowed to remember $O(1)$ vertices (since each vertex takes up $\Theta(\log n)$ space).

If we want to check that there exists a path of length $\ell$, we can simply guess the path vertex-by-vertex and check that it leads from $s$ to $t$; this only requires counting up to $\ell$, which takes logarithmic space (since we're only interested in $\ell &lt; n$). But it's not so clear how to check that there doesn't exist a path of length $\ell$ – what would be a witness for that?

The solution is to use the technique of inductive counting, invented for the proof of the Immerman–Szelepcsényi theorem, which states that NL=coNL. This is what the solution uses.