Open AccessSearching Constant Width Mazes Captures the AC0 Hierarchy
Author(s) -
David A. Mix Barrington,
Chi-Jen Lu,
Peter Bro Miltersen,
Sven Skyum
Publication year - 1997
Publication title -
brics report series
Language(s) - English
Resource type - Journals
eISSN - 1601-5355
pISSN - 0909-0878
DOI - 10.7146/brics.v4i25.18951
Subject(s) - constant (computer programming) , hierarchy , combinatorics , mathematics , upper and lower bounds , discrete mathematics , binary logarithm , grid , algebraic number , computer science , geometry , mathematical analysis , economics , market economy , programming language
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.