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