Time and Space Complexity Classes of Hyperbolic Cellular Automata

Chuzo IWAMOTO, Maurice MARGENSTERN

Summary :

This paper investigates relationships among deterministic, nondeterministic, and alternating complexity classes defined in the hyperbolic space. We show that (i) every t(n)-time nondeterministic cellular automaton in the hyperbolic space (hyperbolic CA) can be simulated by an O(t⁴(n))-space deterministic hyperbolic CA, and (ii) every t(n)-space nondeterministic hyperbolic CA can be simulated by an O(t²(n))-time deterministic hyperbolic CA. We also show that n^r+-time (non)deterministic hyperbolic CAs are strictly more powerful than n^r-time (non)deterministic hyperbolic CAs for any rational constants r 1 and > 0. From the above simulation results and a known separation result, we obtain the following relationships of hyperbolic complexity classes: P_h= NP_h = PSPACE_h EXPTIME_h= NEXPTIME_h = EXPSPACE_h , where C_h is the hyperbolic counterpart of a Euclidean complexity class C. Furthermore, we show that (i) NP_h AP_h unless PSPACE = NEXPTIME, and (ii) AP_h EXPTIME _h.

• Publication: IEICE TRANSACTIONS on Information Vol.E87-D No.3 pp.700-707
• Publication Date: 2004/03/01
• Type of Manuscript: Special Section PAPER (Special Section on Cellular Automata)

Authors

Chuzo IWAMOTO
Maurice MARGENSTERN

Keyword

cellular automata,  complexity classes,  hyperbolic space