ECCC-Report TR97-044https://eccc.weizmann.ac.il/report/1997/044Comments and Revisions published for TR97-044en-usFri, 26 Sep 1997 16:23:05 +0200
Paper TR97-044
| Searching constant width mazes captures the AC^0 hierarchy |
David Mix Barrington,
Chi-Jen Lu,
Peter Bro Miltersen,
Sven Skyum
https://eccc.weizmann.ac.il/report/1997/044
We show that searching a width k maze is complete for \Pi_k, i.e., for
the k'th level of the AC^0 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.
Fri, 26 Sep 1997 16:23:05 +0200https://eccc.weizmann.ac.il/report/1997/044