A space lower bound for st-connectivity on node-named JAGs

AbstractGiven a directed graph G and two of its nodes s and t, the directed st-connectivity problem (stcon) is to decide whether there is a directed path from s to t in G. Establishing a super-logarithmic space lower bound for stcon on a general computation model such as Turing machine or branching program has been a big challenge in complexity theory. As an intermediate step, Cook and Rackoff (SIAM J. Comput. 9(3) (1980) 636–652) introduce a structured model called JAG (jumping automaton for graphs) and prove a space lower bound of Ω(log2n/loglogn) on this model. Berman and 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 Ω(log2n/loglogn). On a probabilistic NNJAG, we show that S=Ω(log2n/(loglogn+loglogT)) 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(log2n/loglogn)