<p>Note: This question is an extension of: <a href="https://cstheory.stackexchange.com/questions/20203/computational-complexity-of-finding-a-1d-deterministic-ca-that-achieves-a-desi#20204">Computational complexity of finding a (1D deterministic) CA that achieves a desired spacetime history &quot;patch&quot; after $t$ iterations</a>, which Marzio De Biasi took time to answer in a very nice manner.</p>

<p>Let $S$ be a spacetime patch (<a href="http://www.wolframscience.com/nksonline/page-960b-text" rel="nofollow noreferrer">http://www.wolframscience.com/nksonline/page-960b-text</a>) 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.</p>

<p>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$.  </p>

<p>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?</p>

<hr>

<p>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$.</p>

<p>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?</p>

<hr>

<p>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:</p>

<p><a href="http://www.wolframalpha.com/input/?i=CA+3-color%2C+range+1%2C+rule+4594122302107" rel="nofollow noreferrer">http://www.wolframalpha.com/input/?i=CA+3-color%2C+range+1%2C+rule+4594122302107</a>
(5th "sub-box" down)</p>

<p>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.</p>

<p>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.  </p>

<p>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.</p>

CC BY-SA 3.0
2013-12-15T15:19:12.447Z
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.
Marzio De Biasi
CC BY-SA 3.0
2013-12-15T15:58:06.583Z
@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.
WShon
CC BY-SA 3.0
2013-12-15T17:32:24.460Z
@MarzioDeBiasi Please let me know if my clarification / example falls short of being helpful.
WShon
CC BY-SA 3.0
2013-12-15T18:49:00.043Z
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.
Marzio De Biasi
CC BY-SA 3.0
2013-12-15T19:30:47.550Z
@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.
WShon
CC BY-SA 3.0
2013-12-15T20:00:14.650Z
but what is the role of the "artificial" grouping of colors (it is a sort of obfuscation, and it is no more a configuration generated by a CA with few colors)? Furthermore you can (try to) apply to CAs some results from Kolmogorov complexity theory: you can easily see that for most (incompressible) configurations there is not a (smaller) CA that can generate them. And what you (formally) mean with "mine the computational universe"? ... Perhaps I should read Wolfram's book :-)
Marzio De Biasi
CC BY-SA 3.0
2013-12-15T20:10:19.780Z
@MarzioDeBiasi I suspect (suspect being the key word) that the natural thing to do when you want to replicate some (say) binary pattern, but you can't reach it with an $n=2$ color CA, is to increase the number of colors in the CA as much as necessary and then perform this repainting procedure at the end to achieve your binary pattern.  How else would you proceed without dropping the constraint on cell-to-cell communication distance?
WShon
CC BY-SA 3.0
2013-12-15T20:13:48.250Z
@MarzioDeBiasi Re: Wolfram's book, you could just watch the talk (http://www.stephenwolfram.com/publications/mining-computational-universe/) :).  What Wolfram means... I think... is that instead of using equations and standard methods to describe the world around us, we can just find a CA that mimics the systems set of states.  Then the rule set for the CA fingerprints the property of the system, or something like that.  Wolfram's NKS is just an enormous set of examples of CA mimicking various phenomena like tapestry weaves, patterns on seashells, and so on.
WShon
CC BY-SA 3.0
2013-12-15T20:17:51.817Z
@MarzioDeBiasi More seriously, I can actually strongly recommend Scott Aaronson's review of NKS (http://www.scottaaronson.com/papers/nks.pdf) which actually contains a really neat proof that local CA cannot properly emulate quantum mechanical phenomena (see section 3.1 on).
WShon
CC BY-SA 3.0
2013-12-15T20:18:20.620Z
Ok, tanks, I'll watch it! But if you pick a random enough pattern of size $m$ the description of the CA that can generate it has size at least $m$. See [Kolmogorov complexity](http://en.wikipedia.org/wiki/Kolmogorov_complexity). I found some works on (in)compressibility theory applied to tag systems, but I think  there are not many papers in this direction for CAs.
Marzio De Biasi
CC BY-SA 3.0
2013-12-15T20:22:22.647Z
@MarzioDeBiasi Thanks - but what do you mean that the CA has to be of size $m$?  Surely you can compress the number of colors with a clever rule set.  I'm trying to get at the hardness of this compression.
WShon
CC BY-SA 3.0
2013-12-15T20:43:20.510Z
@MarzioDeBiasi Anyway, it would be helpful to know if this compression procedure is at least NP-complete.
WShon
<cc.complexity-theory><cellular-automata>
Finding a cellular automaton that reproduces a finite-sized spacetime patch with reduced coloration
WShon
# Finding a cellular automaton that reproduces a finite-sized spacetime patch with reduced coloration

(Asked by: username_0 on 2013-12-15)

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](https://cstheory.stackexchange.com/questions/20203/computational-complexity-of-finding-a-1d-deterministic-ca-that-achieves-a-desi#20204), 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.

**Tags:** cc.complexity-theory, cellular-automata
> **Comments:**
> **username_1**: 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.  
> **username_0**: @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.  
> **username_0**: @MarzioDeBiasi Please let me know if my clarification / example falls short of being helpful.  
> **username_1**: 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.  
> **username_0**: @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.  
> **username_1**: but what is the role of the "artificial" grouping of colors (it is a sort of obfuscation, and it is no more a configuration generated by a CA with few colors)? Furthermore you can (try to) apply to CAs some results from Kolmogorov complexity theory: you can easily see that for most (incompressible) configurations there is not a (smaller) CA that can generate them. And what you (formally) mean with "mine the computational universe"? ... Perhaps I should read Wolfram's book :-)  
> **username_0**: @MarzioDeBiasi I suspect (suspect being the key word) that the natural thing to do when you want to replicate some (say) binary pattern, but you can't reach it with an $n=2$ color CA, is to increase the number of colors in the CA as much as necessary and then perform this repainting procedure at the end to achieve your binary pattern.  How else would you proceed without dropping the constraint on cell-to-cell communication distance?  
> **username_0**: @MarzioDeBiasi Re: Wolfram's book, you could just watch the talk (http://www.stephenwolfram.com/publications/mining-computational-universe/) :).  What Wolfram means... I think... is that instead of using equations and standard methods to describe the world around us, we can just find a CA that mimics the systems set of states.  Then the rule set for the CA fingerprints the property of the system, or something like that.  Wolfram's NKS is just an enormous set of examples of CA mimicking various phenomena like tapestry weaves, patterns on seashells, and so on.  
> **username_0**: @MarzioDeBiasi More seriously, I can actually strongly recommend Scott Aaronson's review of NKS (http://www.scottaaronson.com/papers/nks.pdf) which actually contains a really neat proof that local CA cannot properly emulate quantum mechanical phenomena (see section 3.1 on).  
> **username_1**: Ok, tanks, I'll watch it! But if you pick a random enough pattern of size $m$ the description of the CA that can generate it has size at least $m$. See [Kolmogorov complexity](http://en.wikipedia.org/wiki/Kolmogorov_complexity). I found some works on (in)compressibility theory applied to tag systems, but I think  there are not many papers in this direction for CAs.  
> **username_0**: @MarzioDeBiasi Thanks - but what do you mean that the CA has to be of size $m$?  Surely you can compress the number of colors with a clever rule set.  I'm trying to get at the hardness of this compression.  
> **username_0**: @MarzioDeBiasi Anyway, it would be helpful to know if this compression procedure is at least NP-complete.  

---

## 0 answers

