Time and Space Complexity Classes of Hyperbolic Cellular Automata(<Special Section>Cellular Automata)

概要

論文の詳細を見る
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^4(n))-space deterministic hyperbolic CA, and (ii) everyt(n)-space non-deterministic hyperbolic CA can be simulated by an O(t^2(n))-time deterministic hyperbolic CA. We also show that w^<r+∈>-time (non)deterministic hyperbolic CAs are strictly more powerful than n^r-lime (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 &subpuls; EXPTIME_h = NEXPTIME_h = EXPSPACE_h &subpuls; ・・・, where C_h is the hyperbolic counterpart of a Euclidean complexity class C. Furthermore, we show that (i) NP_h &subpuls; AP_h unless PSPACE = NEXPTIME, and (ii) AP_h ⊆ EXPTIME_h.
社団法人電子情報通信学会の論文
2004-03-01