Constrained Eden
Steve Seif
Mathematics Department
University of Louisville
Louisville, KY 40292, USA
swseif01@louisville.edu
Abstract
Let CA be a one-dimensional cellular automaton. A computational complexity problem, the Constrained Eden problem, denoted C-EDEN(CA), is introduced. C-EDEN(CA) is a finitary variant of the Garden of Eden problem. Even for certain elementary cellular automata, C-EDEN(CA) is NP-complete, providing the first examples of NP-complete problems associated with cellular automata over a two-element alphabet.
