Searching Constant Width Mazes Captures the AC0 Hierarchy


  • David A. Mix Barrington
  • Chi-Jen Lu
  • Peter Bro Miltersen
  • Sven Skyum



We 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).