Two-dimensional majority rule prediction is computationally hard
The Two-Dimensional Majority Rule is P-Complete
Discrete Mathematics
Summary
This paper solves a long-standing question about predicting how a simple system evolves where each cell updates based on the majority of its neighbors. The authors show that determining the future state of a cell in a two-dimensional grid is as hard as many complex problems in computer science, meaning there is unlikely to be a fast, parallel method for prediction. They do this by cleverly encoding information in the timing of signals to simulate logical circuits within the system. This result applies to various similar rules, including those where cells follow the minority instead of the majority.
What this means in practice
- •For parallel algorithm designers: Avoid efforts to design efficient parallel prediction algorithms for two-dimensional majority-rule systems, as the problem is proven to be inherently sequential.
- •For complex system modelers: Use the timing-based encoding techniques to represent complex logical operations within simple two-dimensional local update systems.
A theory result. No direct application yet.
Authors
Pedro Montealegre, Martín Ríos-Wilson
Abstract
We prove that prediction for the synchronous two-dimensional majority rule is $\mathrm{P}$-complete under logspace many-one reductions, resolving a problem open for almost three decades. In 1997, Moore established $\mathrm{P}$-completeness in dimension three and higher and conjectured that the two-dimensional case admits an efficient parallel algorithm. We consider an $n\times n$ torus on which each cell follows the majority of its four nearest neighbors and retains its current state in a tie. Given an explicitly specified initial configuration and a time $T$, prediction asks whether a designated cell is in state $+1$ at time $T$. The central challenge is to make independent information streams cross in the plane under a homogeneous, monotone, diffusive local rule. We overcome this obstacle through a temporal encoding of Boolean values: both values generate activity, but are distinguished by signal arrival times. This encoding yields a crossover that preserves both values and composes with wires, duplication, and AND and OR gates to simulate arbitrary monotone Boolean circuits. Thus a local rule that favors agreement can nevertheless transport, combine, and cross independent information in two dimensions. We also prove $\mathrm{P}$-completeness for deciding whether a designated cell ever reaches $+1$, without a prescribed time horizon. The prediction result extends to every uniform symmetric signed majority rule on the same neighborhood, including the minority rule.