Computations on Nondeterministic Cellular Automata

Abstract

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^{\frac{1}{r+1}}{S}^{\frac{r}{r+1}})$ and by $r+1$-dimensional NCA with time and space complexity $O(T^{1/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 $T_{r,P}$ is time complexity of a fastest $r$-dimensional NCA computing predicate $P$ then $T_{r+1,P} &=O((T_{r,P})^{1-r/(r+1)^2})$, $T_{r-1,P} &=O((T_{r,P})^{1+2/r})$. Similar problems for deterministic CA are discussed.

18 pages in AmsTex, 3 figures in PostScript