On the Computational Complexity of Finite Cellular Automata

作者:

Highlights:

摘要

We study the computational complexity of several problems with the evolution of configurations on finite cellular automata. In many cases, the problems turn out to be complete in their respective classes. For example, the problem of deciding whether a configuration has a predecessor is shown to be NLOG-complete for one-dimensional cellular automata. The problem is NP-complete for all dimensions higher than one. Similarly, the question whether a target configuration occurs in the orbit of a source configuration may be P-complete, NP-complete or PSPACE-complete, depending on the type of cellular automaton.

论文关键词:

论文评审过程:Available online 25 May 2002.

论文官网地址:https://doi.org/10.1006/jcss.1995.1009