Computational Complexity in the Hyperbolic Plane

摘要

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 lim_(n→∞) ((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).