we solve this with BFS or DFS; but those algorithms’ working sets require linear space. Turns out, we can solve this algorithm \text{STCONN} \in \text{SPACE}\left(\log^{2}\left(n\right)\right) for directed G, we are not sure if its in L. for undirected G, Omer showed that its in L open problem: Savitch’s Algorithm is really really slow; we are not sure if there is an algorithm in which we can solve it in better time. Savitch’s Algorithm Savitch’s Algorithm is a middle-first search scheme for solving STCONN. key observation: if there is a path form s \to t of length n, then there must be a point w such that s\to w in \frac{n}{2} steps and w \to t in \frac{n}{2} steps. Goal: brute force search for this w. There is n possibilities for w, we shall just try all of them! This engenders a more general problem named PATH: \text{STCONN}\left(s,t\right) = \text{PATH}\left(s,t,\ceil{\log n}\right) PATH \begin{equation} \text{PATH}\left(x,y,k\right): \text{does there exist path of length \leq 2^{k} from x to y} \end{equation} solution: if k = 0, then return TRUE IFF \left(x,y\right) \in E \vee x = y (that x and y are adjacent or identical) else for each w \in V if \text{PATH}\left(x,w,k-1\right) \wedge \text{PATH}\left(w,y,k-1\right), return TRUE return FALSE space of this:

because for every w, we need to track \log n possible w, and then also need to recurse down to keep track the two \text{PATH} calls; in particular, we recuse the two recurse PATH calls to prevent exponential growth. This gives S(t) = O\left(k \log n\right), so for k = \log n, we have S \left(\log n\right) = O \left(\log^{2} n\right) time of this:

so for k = \log n (n nodes), then T \left(\log n\right) = n^{O \left(\log n\right)} because we can’t recuse time, so the 2 times factor exsits. STCONN is in NL see STCONN is in NL