# Show that problem of Shortest-Path in digraph is in NL

Look at solution to exercise 2, please.
Exercise and solution is derieved from: https://people.eecs.berkeley.edu/~luca/cs172-07/solutions/sol8.pdf

$$ShortestPath = \{(G, k, s, t)| \text{the shortest path from s to > t in G has length k}\}$$ (a) Prove that $ShortestPath$ is in $NL$.

(a) Solution: We construct a $NL$-machine for ShortestPath as follows: on input $\langle G, k, s, t\rangle$, first compute $r_{k−1}$ (the number of vertices reachable from $s$ in at most $k − 1$ steps). Then, on input $\langle G = (V, E), k, s, t\rangle$ and $r_{k−1}$ on the work tape,

d ← 0
flag ← FALSE
for all w ∈ V do
p ← s
for i ← 1 to k − 1 do
non-deterministically pick a neighbor q of p
if p = w then
d ← d + 1
if w = t reject
if w is a neighbor of t then
flag ← TRUE
if d < r_{k−1} reject
if flag then accept else reject


I don't know why it is so complex.
Tell me please, why direct and simple algorithm is not ok:
Check if there exists path from $s$ to $t$ of length $1$
Check if there exists path from $s$ to $t$ of length $2$
...
Check if there exists path from $s$ to $t$ of length $k-1$
If there exists path of length $\le k -1$ then reject. Else check if exists length of $k$ and accept if exists.

In other words we check one be one each length. We can check existence of path thanks to non-determinism. We launch number of visited nodes and check if we end up in $t$

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 < 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?
• When it comes to my solution. I must remember nodes on path to avoid cycles ? I thought that I give algorithm in $P^{NL}$, not $NL$ because I use some sub-algorithm in $NL$ as oracle. Hmm ? Aug 28 '17 at 18:27
• I don't know about your algorithm, but the question asks for an algorithm which can be implemented by an NL machine. Indeed, $P^{NL} = P$, which is conjectured to be larger than $NL$. Aug 28 '17 at 18:28
• @Yuval could you look at me approach in question ? Is it $P^{NL}$ or $NL$? Aug 28 '17 at 18:45
• No need for all the question marks. I suggest that you try to write an algorithm $A(G,s,t,\ell,w)$, where $w$ is a witness, using logarithmic space, with the following two properties: (1) if there is no path of length $\ell$ from $s$ to $t$ in $G$ then there exists a witness $w$ such that the algorithm accepts, (2) if there is a path of length $\ell$ from $s$ to $t$ in $G$ then the algorithm rejects for all witnesses $w$. Aug 28 '17 at 19:33