1
$\begingroup$

Note: This question is an extension of: Computational complexity of finding a (1D deterministic) CA that achieves a desired spacetime history "patch" after $t$ iterations, which Marzio De Biasi took time to answer in a very nice manner.

Let $S$ be a spacetime patch (http://www.wolframscience.com/nksonline/page-960b-text) with $n$-colors corresponding to a one-dimensional deterministic cellular automata $(Q,\sigma)$. I generate a reduced coloring spacetime patch $S_r$ by partitioning the $n$ colors in $S$ into subsets, and then repainting $S$ s.t. any two colors in the same subset will now have the same color. For example, $S$ could have cells colored {Red, Green, Yellow, Blue}, but to generate $S_r$, we form the subsets {{Red}, {Green, Yellow, Blue}}, and repaint the Red cells WHITE, and the Green/Yellow/Blue cells BLACK.

Next, I tell you the value of $n$, i.e. the original number of colors in $S$, I explain how the colors were partitioned into subsets, and I define the strictly local communication rules between cells (e.g. I could say that communication between cells defined by a 3-neighbor von Neumann relation). However, I only provide you the reduced coloration spacetime patch $S_r$.

Your task is to come up with an $n$-color $k$-state one-dimensional deterministic CA that accurately generates $S_r$ after some color partitioning and repainting procedure that (a) could be the same as the one I describe, or (b) could be something novel. What is the computational complexity of your task?


My intuition says that this problem should become impractical to solve in the worst-case as the number of colors increases to somewhere between $n = 10$ to $100$, and where we have spacetime patches that sample a sufficiently large fraction of possible CA states. Here, there should be a combinatoric explosion in the number of possible color assignments to the monochromatic neighborhoods in $S_r$.

Admittedly this could be wrong, but if it is the case, it isn't clear to me what complexity class this problem should fall into. Is it NP-complete but not PSPACE complete, for example?


For an example of what I'm trying to do, here's a deterministic one-dimensional CA with $n = 3$ colors initiating from random initial conditions:

http://www.wolframalpha.com/input/?i=CA+3-color%2C+range+1%2C+rule+4594122302107 (5th "sub-box" down)

Now imagine I repaint the cells in the spacetime patch shown in the above link, e.g. by taking the {0, 1, 2} colors, making the subsets {{0, 1}, {2}}, and then painting the 0 and 1 cells WHITE and the 2 cells BLACK. Call this repainted spacetime patch $S_r$. I then ask you to come up with an $n=3$ color CA that can reproduce the provided spacetime patch $S_r$ by running the CA for an appropriate number of iterations $t$ to generate a spacetime patch of the right size, and then performing a recoloration as you see fit.

You might be able to do the above without needing $n = 3$ colors. If so, that's fantastic. But in the worst case, you'll run into trouble, because we're restricting long-range communication between cells (i.e. cells can only communicate with their nearest-neighbors) so you'll encounter situations where there aren't enough states to get away with fewer colors.

Said differently, the number of global configurations for a deterministic one-dimensional CA is at most $n^j$ (or $n^j \times$ (number of possible CA rules) for all possible $n$-color 1D cellular automata) where $j$ is the number of cells in CA's initial state. The total number of global configurations, the vast majority unreachable by the $n$-color CA, is $n^{(j*t)}$ where $j \times t$ is the size of the spacetime patch. So more colors mean more possible CA configurations for the same size initial input, and thus, the repainted $S_r$ could easily correspond to a global configuration that can't be reached by a CA with fewer than the number of colors used to generate the spacetime patch $S$ prior to the repainting procedure.

$\endgroup$
  • $\begingroup$ Perhaps the question is ill defined: suppose that $n=8$ ($S$ contains 8 colors) and the partition $S_r$ contains only black and white; then I can give you an $n$ color CA that uses the first two colors to generate $S_r$ and the rules for others colors are the same of color 2 (and use the partition {{1},{2,3,4,5,6,7,8}}. You should put a small example (a figure) in which you show what is the input of the algorithm (and other numerical parameters), and what is the desired output. $\endgroup$ – Marzio De Biasi Dec 15 '13 at 15:19
  • $\begingroup$ @MarzioDeBiasi I have updated my question (at the bottom) with an example (appealing to an output of WolframAlpha) and a clarification for where I think there could be trouble. The idea is that more colors for an initial condition means a larger set of possible global configurations. Thus, one might not be able to get away with reproducing $S_r$ with only BLACK and WHITE cells by just assuming its the output of some $2 < n$ state CA. $\endgroup$ – WShon Dec 15 '13 at 15:58
  • $\begingroup$ @MarzioDeBiasi Please let me know if my clarification / example falls short of being helpful. $\endgroup$ – WShon Dec 15 '13 at 17:32
  • $\begingroup$ ok thanks! now it is clear. But the problem is rather artificial: you are asking to find a CA that can reconstruct an "obfuscated" spacetime history $S_r$ (using a non reversible color grouping). However if the number of colors is small enough with respect to the input size m ($n \simeq \log m$) then you can still scan all combinations and solve the problem in polynomial time. Are there interesting consequences if the problem turns out to be polynomial-time solvable (or PSPACE COMPLETE)? Note that a similar problem can be asked for Turing machines. $\endgroup$ – Marzio De Biasi Dec 15 '13 at 18:49
  • $\begingroup$ @MarzioDeBiasi My goal here is to have something very concrete to say in response to claims that, in the general case, one can easily "mine the computational universe" to find a CA that generates some pattern. That the space of patterns that can be generated by CA with few colors is small with respect to the number of global configurations (most not reachable by the CA) and trying to get around this by artificially increasing the number of colors leads to computationally prohibitive color/state assignment search and testing times. $\endgroup$ – WShon Dec 15 '13 at 19:30

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.