Tight lower bounds for st-connectivity on the NNJAG model

Directed st-connectivity is the problem of deciding whether or not there exists a path from a distinguished node s to a distinguished node t in a directed graph. We prove a time-space lower bound on the probabilistic NNJAG model of Poon [Proc. 34th Annual Symposium on Foundations of Computer Science, Palo Alto, CA, 1993, pp. 218-227]. Let n be the number of nodes in the input graph and S and T be the space and time used by the NNJAG, respectively. We show that, for any delta > 0, if an NNJAG uses space S is an element of O(n(1-delta)), then T is an element of 2(Omega(log2 (n/S))); otherwise T is an element of 2(Omega(log2 (n log n/S)/ log log n)) x (nS/ log n)(1/2). (In a preliminary version of this paper by Edmonds and Poon [Proc. 27th Annual ACM Symposium on Theory of Computing, Las Vegas, NV, 1995, pp. 147-156.], a lower bound of T is an element of 2(Omega(log2 (n log n/S)/ log log n)) x (nS/ log n)(1/2) was proved.) Our result greatly improves the previous lower bound of ST is an element of Omega(n(2) / log n) on the JAG model by Barnes and Edmonds [Proc. 34th Annual Symposium on Foundations of Computer Science, Palo Alto, CA, 1993, pp. 228-237] and that of (ST)-T-1/3 is an element of Omega(n(4/3)) on the NNJAG model by Edmonds [Time-Space Lower Bounds for Undirected and Directed ST-Connectivity on JAG Models, Ph.D. thesis, University of Toronto, Toronto, ON, Canada, 1993]. Our lower bound is tight for S is an element of O(n(1-delta)), for any delta > 0, matching the upper bound of Barnes et al. [Proc. 7th Annual IEEE Conference on Structure in Complexity Theory, Boston, MA, 1992, pp. 27-33]. As a corollary of this improved lower bound, we obtain the first tight space lower bound of Omega(log(2) n) on the NNJAG model. No tight space lower bound was previously known even for the more restricted JAG model.