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

• read carefully p2: a configuration is an infinite string/ tape sequence and a subconfiguration is finite. these are not generally std terms in the field however. anyway $K$ is a count of cells and also time steps. its just a bound, it can be generalized ($K \neq Z)$ to different step/ cell differences based on "padding" technique typically.
– vzn
Apr 21, 2016 at 1:02
• So i can say the pre-image problem is nothing but a simulation of other structures in CA (generally) right ? Apr 21, 2016 at 6:23

## 1 Answer

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

• Thanks Ran it is more easy to understand now (hope the question gets solved someday) ... Apr 22, 2016 at 20:53