Complexity of the Freezing Majority Rule with L-shaped Neighborhoods
Fuente:
arXiv
Saved in:
| Main Authors: | , , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866916958084005888 |
|---|---|
| author | Concha-Vega, Pablo Goles, Eric Montealegre, Pedro Perrot, Kévin |
| author_facet | Concha-Vega, Pablo Goles, Eric Montealegre, Pedro Perrot, Kévin |
| contents | In this article we investigate the computational complexity of predicting two dimensional freezing majority cellular automata with states $\{-1,+1\}$, where the local interactions are based on an L-shaped neighborhood structure. In these automata, once a cell reaches state $+1$, it remains fixed in that state forever, while cells in state $-1$ update to the most represented state among their neighborhoods. We consider L-shaped neighborhoods, which mean that the vicinity of a given cell $c$ consists in a subset of cells in the north and east of $c$.
We focus on the prediction problem, a decision problem that involves determining the state of a given cell after a given number of time-steps. We prove that when restricted to the simplest L-shaped neighborhood, consisting of the central cell and its nearest north and east neighbors, the prediction problem belongs to $\mathsf{NC}$, meaning it can be solved efficiently in parallel. We generalize this result for any L-shaped neighborhood of size two. On the other hand, for other L-shaped neighborhoods, the problem becomes $\mathsf{P}$-complete, indicating that the problem might be inherently sequential. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2509_16065 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Complexity of the Freezing Majority Rule with L-shaped Neighborhoods Concha-Vega, Pablo Goles, Eric Montealegre, Pedro Perrot, Kévin Computational Complexity Discrete Mathematics In this article we investigate the computational complexity of predicting two dimensional freezing majority cellular automata with states $\{-1,+1\}$, where the local interactions are based on an L-shaped neighborhood structure. In these automata, once a cell reaches state $+1$, it remains fixed in that state forever, while cells in state $-1$ update to the most represented state among their neighborhoods. We consider L-shaped neighborhoods, which mean that the vicinity of a given cell $c$ consists in a subset of cells in the north and east of $c$. We focus on the prediction problem, a decision problem that involves determining the state of a given cell after a given number of time-steps. We prove that when restricted to the simplest L-shaped neighborhood, consisting of the central cell and its nearest north and east neighbors, the prediction problem belongs to $\mathsf{NC}$, meaning it can be solved efficiently in parallel. We generalize this result for any L-shaped neighborhood of size two. On the other hand, for other L-shaped neighborhoods, the problem becomes $\mathsf{P}$-complete, indicating that the problem might be inherently sequential. |
| title | Complexity of the Freezing Majority Rule with L-shaped Neighborhoods |
| topic | Computational Complexity Discrete Mathematics |
| url | https://arxiv.org/abs/2509.16065 |