6
$\begingroup$

$ST-CONN = \text{{(G,s,t) | G is directed graph, there's path from s to t}}$
I've learned the following deterministic algorithm to solve the problem in $log^2n$ space:
$\psi(G,s,t,k) :$
$\hspace{1cm}\text{if k == 1: return 1 if there's edge from s to t, else return 0;}$
$\hspace{1cm}\text{foreach } v \in V(G) \text{:}$
$\hspace{2cm}L=\psi(G,s,v,\lceil{\frac{k}{2}}{\rceil});$
$\hspace{2cm}R=\psi(G,v,t,\lfloor{\frac{k}{2}}{\rfloor});$
$\hspace{2cm}\text{if L == 1 and R == 1, return 1;}$
$\hspace{1cm}\text{return 0;}$
The professor said in class that the algorithm takes at most $\mathcal{O}(\log^2n)$ space, where $n$ is the number of vertices. But don't we pass the entire graph each call? I'll expect to see a $|V|+|E|$ factor in the big-oh, or maybe I miss something here.

$\endgroup$
6
$\begingroup$

You don't need to pass $G$ every time, since it doesn't change across calls. You can think of it as a global variable, which is stored only on the input tape. The other parameters take only $O(\log n)$ steps, and since the depth of the call stack is also $O(\log n)$, in total this uses up $O(\log^2 n)$ space on the work tape.

$\endgroup$
  • $\begingroup$ I thought about treating G like a global variable but I didn't know how to translate that into TM, thanks Yuval! $\endgroup$ – sel Jul 13 '16 at 20:17

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.