What does Cellular Automata Pre-image problem actually means?

I am reading about Cellular Automata and Computational Complexity and i found a related paper by F. Green, NP-Complete Problems in Cellular Automata.

In the 2nd page he lists three NP-Complete problems related to CA, the first problem is:


CA preimage : Given a subconfiguration of length $K$, is there a configuration that could have led to it in $K$ time steps ?

I am confused with the term "Sub-configuration" and its meaning, in the paper he states that a Sub-configuration is contagious states in a finite array.

1- Does it mean a structure like Rule 110 or 90 - ECA at length $K$ ?

2- Or does it mean a pattern generated after $K$ time step in a specific structure (i.e a pattern in rule 110) ?

3- Why the problem states that the subconfiguration's length should equal to the time steps it was generated in ? what if the problem was solvable in $K$ time steps but with a constant time steps $Z$ ?

The way I understand it, the answer is your item #2.

That is, the specific CA is fixed (i.e., rule 90 or rule 110, or what ever), and given that fixed CA, one gives you a (sub)configuration, and asks whether there exists another configuration that leads to the input (sub)configuration within $K$ steps.

Indeed the description there (in the introduction of the paper) is very informal, but this is only because the
the problem is formally stated in section 3:


CAP (CA Preimage problem):

Given: A fixed CA $(Q,\delta)$ and a configuration substring $s$.

Question: Is there a configuration substring $s_0$ such that $s_0 \vdash^{K} s$, where $K= |s|$?

StackExchange Computer Science Q#56264, answer score: 4