2 grammer fixing

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

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

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

1

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