## 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.