Consider the problem of finding a minimum $n$-color $k$-state one-dimensional cellular automata (minimizing $k$ for some fixed value of $n$ or vice versa), with communication between cells defined by a 3-neighbor von Neumann relation, that recreates some fixed-size spacetime history "patch" (http://www.wolframscience.com/nksonline/page-960b-text) of an unknown cellular automata (e.g. some output of Wolfram's pseudorandom Rule 30 CA: http://en.wikipedia.org/wiki/Rule_30) initiating from a known seed of some specified size and geometry and evolved for $t$ iterations. Informally speaking, provided an array corresponding to an unknown n-color k-state CA evolved for a known number of iterations from a defined seed specifying initial conditions, can you provide me a sufficiently minimal CA to create given pattern (with the full understanding that there may be a diverse and non-unique set of solutions)?
Now let me make a strong (and possibly false) statement: "There is no known computational complexity for this problem, and in the general case, exhaustive search must be employed over the set of all possible $n$-color $k$-state cellular automata (with communication between cells defined by a 3-neighbor von Neumann relation) to find a minimal cellular automata capable of recreating a specified spacetime history provided an initial seed of some defined size and geometry. This is true even if we specify that $n = 2$, as for example Wolfram does for all of his elementary CA patterns. This is true regardless of any guarantee about the properties of the initial seed as long as $r$, the number of cells in the seed, is $<<N$, the number of cells in the specified spacetime history."
To what extent is the above statement true, and are there any good literature references that make any strong statements about the computational complexity of this problem? I've been able to find a lot of papers in the literature that talk about, say, using evolutionary algorithms to solve this so-called "cellular automata inverse" problem, but almost nothing that touches on the general case computational complexity of the problem.
Motivation: In Stephen Wolfram's "New Kind of Science", the central argument of the book seems to be that one can "mine the computational universe" for cellular automaton rules that at least emulate everything from patterns appearing on seashells and stripes on a zebras, to local deterministic models of reality (proven aphysical in Scott Aaronson's review of NKS (section 3.2): http://www.scottaaronson.com/papers/nks.pdf).
Saying nothing about whether emulating some pattern or process in nature yields insight into the underlying rules for the process, I'd like to be able to say something specific about the "hardness" of trying to actually actually emulate some fixed sized pattern with a sufficiently simple $n$-color $k$-state CA.
Update: Why is this problem not the Configuration REachability Problem (CREP)?
Quickly, and to simplify matters, I'd like to further specify that the one-dimensional CA we consider here should be deterministic in one direction, though not necessarily invertible (i.e. they could involve cumulative XOR calculations). Initial conditions (i.e. seed values) are always defined.
Now, the Configuration REachability Problem (CREP) asks if a given cellular automaton in one state, $X$, can evolve in some number of iterations $t$ to reach a state $Y$. This diverges from my question in two important ways:
(1) I'm not specifying a cellular automata. The problem is to find one that is sufficiently simple to reproduce some provided (finite) spacetime history (i.e. where the number of states or colors is restricted or minimized). This is not a straightforward decision problem.
(2) I'm interested in finding a CA that not only reaches the current state of a given spacetime history, but the entirety of the spacetime history. For example, if I run Wolfram's Rule 30 for some number of iterations from a one-dimensional seed of length $L$, making a triangle with a pseudo-random pattern, I would then simply give you an array encoding this triangle, and your job would be to find a simple $n = 2$ state cellular automata (minimizing for colors) that reproduces the triangle starting from the same initialization conditions.
In any case, for a deterministic one-dimensional CA starting from known initial conditions, determining reachability should be a matter of simply simulating the CA for a sufficiently time to generate the provided finite spacetime history.