\input zb-basic
\input zb-ioport
\iteman{io-port 01454568}
\itemau{Poon, C.K.}
\itemti{A space lower bound for $st$-connectivity on node-named JAGs.}
\itemso{Theor. Comput. Sci. 237, No.1-2, 327-345 (2000).}
\itemab
Summary: Given a directed graph $G$ and two of its nodes $s$ and $t$, the directed $st$-connectivity problem ($st$con) is to decide whether there is a directed path from $s$ to $t$ in $G$. Establishing a super-logarithmic space lower bound for $st$con on a general computation model such as Turing machine or branching program has been a big challenge in complexity theory. As an intermediate step, {\it S. A. Cook} and {\it C. W. Rackoff} [SIAM J. Comput. 9, 636-652 (1980; Zbl 0445.68038)] introduce a structured model called JAG (jumping automaton for graphs) and prove a space lower bound of $\Omega(\log^{2}n/\log \log n)$ on this model. {\it P. Berman} and {\it J. Simon} (Proc. 24th Annual Symp. on Foundations of Computer science, IEEE press, New York, Tucson, AZ, November 1983) show a similar lower bound for a probabilistic JAG. We take a step further by introducing a stronger model called NN-JAG (Node-named JAG) and obtain the same space lower bound of $\Omega(\log^{2}n/\log \log n)$. On a probabilistic NNJAG, we show that $S=\Omega(\log^{2}n/(\log \log n+\log \log T))$ where $S$ is the space and $T$ is the expected time used, respectively. This gives the best expected time lower bound on this model when the space $S$ is $O(\log^{2}n/\log \log n)$.
\itemrv{~}
\itemcc{}
\itemut{graph; connectivity; lower bound; space; complexity}
\itemli{doi:10.1016/S0304-3975(00)00019-0}
\end