NP-Complete Problems in Cellular Automata
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.
