1998/01/16 by Yuri Ozhigov
Physics and Astronomy · #comp-gas #nlin.CG
published as Information and Computation 148, 181-201 (1999) · 18 pages in AmsTex, 3 figures in PostScript
arxiv created 1998/01/16 · arxiv updated 2009/11/30
The work is concerned with the trade-offs between the dimension and the time and space complexity of computations on nondeterministic cellular automata. It is proved, that 1). Every NCA \Cal A of dimension r, computing a predicate P with time complexity T(n) and space complexity S(n) can be simulated by r-dimensional NCA with time and space complexity O(T(1)/(r+1) S(r)/(r+1)) and by r+1-dimensional NCA with time and space complexity O(T1/2 +S). 2) For any predicate P and integer r>1 if \Cal A is a fastest r-dimensional NCA computing P with time complexity T(n) and space complexity S(n), then T= O(S). 3). If Tr,P is time complexity of a fastest r-dimensional NCA computing predicate P then Tr+1,P &=O((Tr,P)1-r/(r+1)2), Tr-1,P &=O((Tr,P)1+2/r). Similar problems for deterministic CA are discussed.