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., Lu, C.-J., Miltersen, P., & Skyum, S. (1997). Searching Constant Width Mazes Captures the AC0 Hierarchy. BRICS Report Series, 4(25).