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$ ?