Abstract
This paper presents simulation and separation results on the computational complexity of cellular automata (CA) in the hyperbolic plane. It is shown that every t(n)-time nondeterministic hyperbolic CA can be simulated by an O(t 3(n))-time deterministic hyperbolic CA. It is also shown that for any computable functions t 1 (n) and t 2 (n) such that limn→∞(t 1(n))3/t 2(n) = 0, t 2(n)-time hyperbolic CA are strictly more powerful than t 1(n)-time hyperbolic CA. This time hierarchy holds for both deterministic and nondeterministic cases. As for the space hierarchy, hyperbolic CA of space s(n) + ε(n) are strictly more powerful than those of space s(n) if ε(n) is a function not bounded by O(1).
This research was supported in part by Scientific Research Grant, Ministry of Education, Japan.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
J. Hartmanis, P.M. Lewis II, and R.E. Stearns, Hierarchies of memory limited computations, in: Proc. IEEE Symp. on Switching Circuit Theory and Logical Design, 1965, 179–190.
J. Hartmanis and R.E. Stearns, On the computational complexity of algorithms, Trans. Amer. Math. Soc., 117 (1965) 285–306.
K. Iwama and C. Iwamoto, Improved time and space hierarchies of one-tape offline TMs, in: Proc. Int’l Symp. on Mathematical Foundations of Computer Science (LNCS1450), 1998, 580–588.
C. Iwamoto, T. Hatsuyama, K. Morita, and K. Imai, Constructible functions in cellular automata and their applications to hierarchy results, Theor. Comput. Sci. 2701/2 (2002) 797–809. (Preliminary version: Proc. 12th Int’l Symp. on Fundamentals of Computation Theory (LNCS1684), 1999, 316–326.)
C. Iwamoto, M. Margenstern, K. Morita, and T. Worsch, P = NP in the space of CA of the hyperbolic plane, Presentation at the 7th Int’l Workshop on Cellular Automata, Automata 2001 (IFIP WG 1.5), Hyères, France, September, 2001.
K. Loryś, New time hierarchy results for deterministic TMs, in: Proc. Int’l Symp. on Theoretical Aspects of Computer Science (LNCS577), 1992, 329–336.
M. Margenstern, New tools for cellular automata in the hyperbolic plane, Journal of Universal Computer Science, 612 (2000) 1226–1252.
M. Margenstern and K. Morita, NP problems are tractable in the space of cellular automata in the hyperbolic plane, Technical report, Publications of the I.U.T. of Metz, 38p. 1998. (Journal version: Theor. Comput. Sci. 259 (2001) 99–128.)
J. Mazoyer, A 6-state minimal time solution to the firing squad synchronization problem, Theoret. Comput. Sci., 50 (1987) 183–238.
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2002 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Iwamoto, C., Andou, T., Morita, K., Imai, K. (2002). Computational Complexity in the Hyperbolic Plane. In: Diks, K., Rytter, W. (eds) Mathematical Foundations of Computer Science 2002. MFCS 2002. Lecture Notes in Computer Science, vol 2420. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-45687-2_30
Download citation
DOI: https://doi.org/10.1007/3-540-45687-2_30
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-44040-6
Online ISBN: 978-3-540-45687-2
eBook Packages: Springer Book Archive