Complex Systems

NP-Complete Problems in Cellular Automata Download PDF

Frederic Green
Department of Mathematics and Computer Science, Clark University,
Worcester, MA 01610, USA

Abstract

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