Searching Constant Width Mazes Captures the AC0 Hierarchy
AbstractWe show that searching a width k maze is complete for Pi_k, i.e.,
for the k'th level of the AC0 hierarchy. Equivalently, st-connectivity
for width k grid graphs is complete for Pi_k. As an application, we
show that there is a data structure solving dynamic st-connectivity for
constant width grid graphs with time bound O(log log n) per operation
on a random access machine. The dynamic algorithm is derived from
the parallel one in an indirect way using algebraic tools.
How to Cite
Barrington, D. A. M., Lu, C.-J., Miltersen, P. B., & Skyum, S. (1997). Searching Constant Width Mazes Captures the AC0 Hierarchy. BRICS Report Series, 4(25). https://doi.org/10.7146/brics.v4i25.18951
Articles published in DAIMI PB are licensed under a Creative Commons Attribution-NonCommercial-NoDerivs 3.0 Unported License.