×

NP-complete problems in cellular automata. (English) Zbl 0648.68067

An example of a cellular automaton (CA) is given in which the following problems are NP-complete: (i) determining if a given subconfiguration s can be generated after \(| s|\) time steps, (ii) determining if a given subconfiguration s will recur after \(| s|\) time steps, (iii) determining if a given temporal sequence of states s can be generated in \(| s|\) time steps. It is also found that the CA constructed has an NP-hard limit language.

MSC:

68Q80 Cellular automata (computational aspects)
68Q25 Analysis of algorithms and problem complexity
PDFBibTeX XMLCite