|
The Immerman-Szelepcsenyi Theorem uses an algorithm for
co-st-connectivity based on inductive counting to prove that
nondeterministic logarithmic space (NL) is closed under
complementation. We want to investigate whether counting is
necessary for this theorem to hold. Concretely, we show that
Nondeterministic Jumping Automata on Graphs (nondeterministic JAGs)
(pebble automata on graphs) can order several families of Cayley
graphs and thus can decide all NL-properties on them, in particular
co-st-connectivity. 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 which according to our results can be ordered include
Cayley graphs for particular presentations of all finite simple
groups and arbitrary wreath products as well as Cayley graphs of
abelian groups irrespective of how they are presented.
We remark that assessing the precise power of nondeterministic JAGs
and in particular 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.
|
