5
$\begingroup$

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

Improve this question
$\endgroup$
2
  • 1
    $\begingroup$ 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. $\endgroup$
    – vzn
    Apr 21, 2016 at 1:02
  • $\begingroup$ So i can say the pre-image problem is nothing but a simulation of other structures in CA (generally) right ? $\endgroup$
    – Henry akpo
    Apr 21, 2016 at 6:23

1 Answer 1

Reset to default
4
$\begingroup$

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

Improve this answer
$\endgroup$
1
  • $\begingroup$ Thanks Ran it is more easy to understand now (hope the question gets solved someday) ... $\endgroup$
    – Henry akpo
    Apr 22, 2016 at 20:53

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.