Time and Space Complexity Classes of Hyperbolic Cellular Automata

Chuzo IWAMOTO; Maurice MARGENSTERN

Time and Space Complexity Classes of Hyperbolic Cellular Automata

Chuzo IWAMOTO, Maurice MARGENSTERN

Full Text Views

0

Share
Cite this

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

Publicized

Online ISSN

DOI

Type of Manuscript: Special Section PAPER (Special Section on Cellular Automata)

Category

Cite this

Copy

Chuzo IWAMOTO, Maurice MARGENSTERN, "Time and Space Complexity Classes of Hyperbolic Cellular Automata" in IEICE TRANSACTIONS on Information, vol. E87-D, no. 3, pp. 700-707, March 2004, doi: .
Abstract: 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.
URL: https://globals.ieice.org/en_transactions/information/10.1587/e87-d_3_700/_p

Copy

@ARTICLE{e87-d_3_700,
author={Chuzo IWAMOTO, Maurice MARGENSTERN, },
journal={IEICE TRANSACTIONS on Information},
title={Time and Space Complexity Classes of Hyperbolic Cellular Automata},
year={2004},
volume={E87-D},
number={3},
pages={700-707},
abstract={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.},
keywords={},
doi={},
ISSN={},
month={March},}

Copy

TY - JOUR
TI - Time and Space Complexity Classes of Hyperbolic Cellular Automata
T2 - IEICE TRANSACTIONS on Information
SP - 700
EP - 707
AU - Chuzo IWAMOTO
AU - Maurice MARGENSTERN
PY - 2004
DO -
JO - IEICE TRANSACTIONS on Information
SN -
VL - E87-D
IS - 3
JA - IEICE TRANSACTIONS on Information
Y1 - March 2004
AB - 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.
ER -