Searching Constant Width Mazes Captures the AC0 Hierarchy

Authors

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

DOI:

https://doi.org/10.7146/brics.v4i25.18951

Abstract

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.

Downloads

Published

1997-01-25

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