arXiv · Oct 3, 2026
The Two-Dimensional Majority Rule is P-Complete
By Pedro Montealegre, Martín Ríos-Wilson
We prove that prediction for the synchronous two-dimensional majority rule is P-complete under logspace many-one reductions, resolving a problem open for almost three decades. In 1997, Moore established P-completeness in dimension three and higher and conjectured that the two-dimensional case admits an efficient parallel algorithm. We consider an n× 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 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.