Abstract
We show that searching a width k maze is complete for Π k, i.e., for the k'th level of the AC 0 hierarchy. Equivalently, st-connectivity for width k grid graphs is complete for Π k. As an application, we show that there is a data structure solving dynamic st-connectivity for con stant 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.
Supported by the ESPRIT Long Term Research Programme of the EU under project number 20244 (ALCOM-IT).
Preview
Unable to display preview. Download preview PDF.
References
D. A. M. Barrington, N. Immerman and H. Straubing. On uniformity within NC 1 Journal of Computer and System Sciences, 4(3):274–306.
D. A. M. Mix Barrington and D. Thérien. Finite monoids and the fine structure of NC1. Journal of the ACM, 35(4):941–952, October 1988.
P. Beame and F. Fich. On searching sorted lists: A near-optimal lower bound. Manuscript, 1997.
M. Blum and D. Kozen. On the power of the compass (or why mazes are easier to search than graphs). In 19th Annual Symposium on the Foundations of Computer Science, pages 132–142, October 1978.
D. Eppstein. Dynamic connectivity in digital images. Technical Report 96-13, Univ. of California, Irvine, Department of Information and Computer Science, 1996.
D. Eppstein, G. Italiano, R. Tamassia, R. E. Tarjan, J. Westbrook, and M. Yung. Maintenance of a minimum spanning forest in a dynamic planar graph. Journal of Algorithms, 13:33–54, 1992.
G. S. Frandsen, P. B. Miltersen, and S. Skyum. Dynamic word problems. Journal of the ACM 44:257–271, 1997.
T. Husfeldt and T. Rauhe. Hardness results for dynamic problems by extensions of Fredman annd Saks chronogram method.. Manuscript, 1997.
N. Immerman. Languages that capture complexity classes.SIAM Journal on Computing, 16(4):760–778, 1987.
N. Immerman and S. Landau. The complexity of iterated multiplication. Information and Computation, 116(1):103–116, January 1995.
A. Itai, C. H. Papadimitriou, and J. L. Szwarcfiter. Hamilton paths in grid graphs. SIAM Journal on Computing, 11(4):676–686, 1982.
J. E. Pin. Varieties of Formal Languages. New York: Plenum Press, 1986.
A. A. Razborov. Lower Bounds for deterministic and nondeterministic branching programs. In L. Budach, ed., Fundamentals of Computation Theory, 8th International Conference: FCT '91. Lecture Notes in Computer Science 529, 47–60. Berlin, Springer Verlag, 1991.
M. Sipser. Borel sets and circuit complexity. In Proceedings, 15th ACM Symposium on the Theory of Computing, 1983, 61–69.
S. Skyum and L. G. Valiant. A complexity theory based on Boolean algebra. Journal of the ACM, 32(2):484–502, April 1985.
W. Thomas. Classifying regular events in symbolic logic. J. Comput. System Sci. 25, 1982, 360–376.
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 1998 Springer-Verlag
About this paper
Cite this paper
Barrington, D.A.M., Lu, CJ., Miltersen, P.B., Skyum, S. (1998). Searching constant width mazes captures the AC 0 hierarchy. In: Morvan, M., Meinel, C., Krob, D. (eds) STACS 98. STACS 1998. Lecture Notes in Computer Science, vol 1373. Springer, Berlin, Heidelberg. https://doi.org/10.1007/BFb0028550
Download citation
DOI: https://doi.org/10.1007/BFb0028550
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-64230-5
Online ISBN: 978-3-540-69705-3
eBook Packages: Springer Book Archive