Computations on Nondeterministic Cellular Automata

Original · EN

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 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¹/ʳ⁺¹ Sʳ/ʳ⁺¹) and by r+1-dimensional NCA with time and space complexity O(T¹/² +S). 2) For any predicate P and integer r>1 if 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ᵣ,ₚ is time complexity of a fastest r-dimensional NCA computing predicate P then Tᵣ₊₁,ₚ &=O((Tᵣ,ₚ)¹⁻ʳ/⁽ʳ⁺¹⁾²), Tᵣ₋₁,ₚ &=O((Tᵣ,ₚ)¹⁺²/ʳ). Similar problems for deterministic CA are discussed.