  The Immerman-Szelepcsenyi Theorem uses an algorithm for co-st- connectivity
based on inductive counting to prove that NLOGSPACE is closed un- der
complementation. We want to investigate whether counting is necessary for this
theorem to hold. Concretely, we show that Nondeterministic Jumping Graph
Autmata (ND-JAGs) (pebble automata on graphs), on several families of Cayley
graphs, are equal in power to nondeterministic logspace Turing machines that
are given such graphs as a linear encoding. In particular, it follows that
ND-JAGs can solve co-st-connectivity on those graphs. This came as a surprise
since Cook and Rackoff showed that deterministic JAGs cannot solve
st-connectivity on many Cayley graphs due to their high self-similarity (every
neighbourhood looks the same). Thus, our results show that on these graphs,
nondeterminism provably adds computational power. The families of Cayley graphs
we consider include Cayley graphs of abelian groups and of all finite simple
groups irrespective of how they are presented and graphs corresponding to
groups generated by various product constructions, in- cluding iterated ones.
We remark that assessing the precise power of nondeterministic JAGs and in par-
ticular whether they can solve co-st-connectivity on arbitrary graphs is left
as an open problem by Edmonds, Poon and Achlioptas. Our results suggest a
positive answer to this question and in particular considerably limit the
search space for a potential counterexample.
