Complexity of the Freezing Majority Rule with L-shaped Neighborhoods
Preprint
Abstract
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.
Keywords
All Related Versions
This publication has 9 references indexed in Scilit:
- On the Complexity of Stable and Biased MajorityMathematics, 2022
- On the complexity of two-dimensional signed majority cellular automataJournal of Computer and System Sciences, 2018
- Freezing period strongly impacts the emergence of a global consensus in the voter modelScientific Reports, 2014
- The complexity of the bootstraping percolation and other problemsTheoretical Computer Science, 2013
- SOCIOPHYSICS: A REVIEW OF GALAM MODELSInternational Journal of Modern Physics C, 2008
- The role of inflexible minorities in the breaking of democratic opinion dynamicsPhysica A: Statistical Mechanics and its Applications, 2007
- Computability. Computable Functions, Logic, and the Foundations of MathematicsThe Bulletin of Symbolic Logic, 2002
- Majority-Vote Cellular Automata, Ising Dynamics, and P-CompletenessJournal of Statistical Physics, 1997
- Consensus in the presence of partial synchronyJournal of the ACM, 1988