  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.
