PaperlayerView exact revision on arXiv

Source-linked AI summary

The Two-Dimensional Majority Rule is P-Complete

Pedro Montealegre, Martín Ríos-Wilson

arXiv:2610.04311v1cs.DM

TL;DR

Exact prediction for the homogeneous synchronous two-dimensional majority rule remained open, in part because independent signals must cross in the plane. The paper uses activation time to encode Boolean values and construct a crossover, proving P-completeness for prediction and extending the result to related prediction questions and rules.

  • Problem

    Whether exact prediction for the homogeneous, unsigned, synchronous two-dimensional majority rule is P-complete remained unresolved, with independent signals difficult to route across the plane without interference.

    Source: §1 · p. 2

  • Method

    A temporal encoding distinguishes Boolean values by signal arrival time and provides a crossover for a reduction from the Monotone Circuit Value Problem.

    Source: §1.2 · p. 3, §2 · p. 6

  • Results

    Prediction for the two-dimensional synchronous majority rule is P-complete, and the temporal construction preserves independent information streams as they cross.

    Source: §1 · p. 2, §5 · p. 28

  • Takeaways & Limitations

    A homogeneous, monotone, diffusive local rule can transport, combine, and cross independent information streams in the plane with enough fidelity to realize P-complete computation.

    Source: §1 · p. 2, §5 · p. 28

    The construction does not immediately extend to the Moore neighborhood, and prediction for the strict majority rule on the Toom neighborhood remains open.

    Source: §5 · p. 29

Abstract

from arXiv · show

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.

1 Introduction

The paper resolves the long-open question of whether exact prediction for the homogeneous synchronous two-dimensional majority rule is P-complete. A temporal encoding makes independent signals cross in the plane, enabling circuit simulation and extending hardness to prediction without a fixed horizon and to related signed rules.

1 Introduction

  • Each cell updates synchronously by the majority of its four nearest neighbors and retains its state when those neighbors are evenly split.The finite-torus dynamics has a period-two eventual orbit and an O(n^2) transient bound, placing prediction in P even for binary-encoded times.Source: §1 · pp. 1–2
  • The unresolved two-dimensional case requires crossing independent signals in a plane where majority interactions tend to make nearby streams interfere.Earlier work established P-completeness in dimension three and higher, where wires can pass over one another.Source: §1 · p. 2

1.1 Prediction problems

  • Prediction asks whether a designated cell is +1 at a specified time; Majority Stability asks whether it ever reaches +1, and both problems belong to P.For an initially −1 target, Majority Stability asks whether it changes to +1; an initially +1 target gives an immediate yes.Source: §1 · p. 2, §1.1 · p. 3

1.2 Our results

  • Prediction for the two-dimensional synchronous majority rule is P-complete under logspace many-one reductions, using a temporal-encoding reduction from the Monotone Circuit Value Problem.The reduction builds a crossover and the other gadgets needed for circuit simulation.Source: §1.2 · p. 3
  • A temporal encoding distinguishes Boolean values by activation time, allowing a crossover that preserves values and supports wires, duplication, AND, and OR gates.The gadgets simulate arbitrary monotone Boolean circuits.Source: §1 · p. 2, §1.2 · p. 3
  • Majority Stability is P-complete, so the construction also establishes hardness when no reading time is specified.A temporal fuse turns an early-versus-late output signal into a persistent state change.Source: §1.2 · p. 3
  • Prediction is P-complete for every uniform symmetric signed majority rule in two dimensions, including the minority and crazy-spin rules.The result transfers through an equivalence established in.Source: §1.2 · pp. 3–4

1.3 Related work

  • Prior work modified aspects of the model to study tractable or hard cases; this paper returns to the homogeneous, unsigned, synchronous rule and exact worst-case prediction.Related work also studies typical behavior under random initial configurations or graphs, unlike this fixed-lattice, explicitly specified worst-case setting.Source: §1.3 · pp. 5–6

2 The gadgets

The section builds an MCVP reduction from wires, turns, crossings, logic gates, and duplication. Its temporal encoding distinguishes Boolean values by activity at scheduled reading times, enabling these gadgets to preserve and combine information.

2.1 Wires and temporal encoding

  • Both Boolean values generate activity, but a value is identified by the cell state at its prescribed reading time; false becomes active two updates later in the same phase.Eventual activation alone does not distinguish the values.Source: §2 · p. 6, §2.1 · p. 7

2.2 Temporal crossover

  • The crossover preserves each input at its corresponding output at a common reading time, even when the two input values differ.The outputs are read at T = 12; two updates later both ports are positive for every input assignment.Source: §2.2 · p. 8

2.3 Right-angle turn

  • A right-angle turn routes either Boolean value around a corner without changing it or its temporal code.Rotated and reflected turns provide the orientations used within square blocks.Source: §2.3 · p. 8

2.4 AND gate

  • The AND gadget passes A through horizontally and outputs A ∧ B vertically, positive at the scheduled time only when both inputs are true.Both outputs are read at T = 10; false conjunctions become positive two updates later.Source: §2.4 · p. 9

2.5 OR gate

  • The OR gadget outputs A ∨ B, positive at its scheduled reading time exactly when at least one input is true.For (A, B) = (0, 0), the output is negative at T = 11 and becomes positive at T + 2.Source: §2.5 · p. 9

2.6 Signal duplicator

  • The duplicator produces two copies of A at a common reading time, making one signal available to multiple destinations.Both outputs reproduce A at T = 13, and both are positive two updates later for either input value.Source: §2.6 · p. 11

2.7 Uniform square blocks

  • Uniform blocks normalize AND, OR, crossover, and duplication to north/west inputs and south/east outputs, with AND and OR results sent to both output sides.AND and OR outputs are assembled with duplicators; crossover routes each input straight through, while duplication uses one input and closes the other side.Source: §2.7 · pp. 11, 14, 17
  • Routes, reading phases, and source-free backgrounds are synchronized so blocks share a common delay and connect across a grid with one update between adjacent blocks.The delay is fixed independently of the simulated circuit, and route adjustments align both arrival times and phases.Source: §2.7 · pp. 14, 17, 19

3 Proof of the main result

The proof reduces monotone circuit evaluation to majority prediction by embedding a logical grid circuit in a two-dimensional torus. Uniform majority-rule blocks implement the grid, with timing and a logspace construction preserving the circuit’s output.

3.1 Circuit value problems

  • MCVP uses constant, AND, and OR gates, and its monotone version remains P-complete, so it suffices as the reduction source.A monotone circuit has no negation gates; its input assignments are represented by constant gates.Source: §3.1 · p. 20

3.2 The reduction scheme

  • The grid routes information east and south, using temporal crossovers, duplicators, and diagonal AND or OR blocks to compute each gate value.The resulting grid circuit has size parameter m, is logspace computable, and outputs (βm, βm) at block (m, m).Source: §3.2 · pp. 20–21

3.3 Grid circuit embedding

  • Adjacent uniform blocks with matching ports continue wire patterns across shared sides, transferring output values to neighboring inputs in one update; the construction has torus side n = O(m) and query time T = O(m).The map from a monotone circuit to the torus side, initial configuration, and query time is logspace computable.Source: §3.3 · pp. 22–24
  • MCVP reduces in logspace to Majority Prediction, whose queried spin is +1 exactly when the input circuit evaluates to 1.Since MCVP is P-complete and Majority Prediction belongs to P, the reduction proves P-completeness.Source: §3.3 · p. 24

4 Extensions

The paper extends hardness to prediction for uniform symmetric signed majority rules and to deciding whether a cell ever reaches +1. A temporal fuse makes an early circuit-output signal persist, while a spin transformation relates signed-rule dynamics to majority dynamics.

4.1 Stability

  • The fuse converts arrival timing into a persistent cell-state distinction: an arrival at E at time 3 sets M to +1 permanently from time 4, while time 5 or no arrival leaves it at −1.Separately, Majority Stability is P-complete.Source: §4.1 · p. 25

4.2 Symmetric signed majority

  • Reversing spins on a selected sublattice, and at odd time steps when a = −1, transforms signed-rule dynamics into majority dynamics.This transformation supports the signed-rule hardness results.Source: §4.2 · p. 28
  • Prediction is P-complete for every uniform symmetric signed majority rule; Stability is also P-complete when the self-interaction sign a is +1.The family includes the minority and crazy-spin rules.Source: §4.2 · pp. 27–28

5 Discussion

The discussion presents temporal encoding as a way to cross independent information streams without changing the homogeneous rule or interaction graph. It distinguishes the settled von Neumann prediction problem from open variants and relates signal propagation to unresolved questions in two-dimensional sandpile prediction.

5 Discussion

  • Temporal encoding lets a homogeneous, diffusive rule cross independent information streams without changing the interaction graph or using cell-specific rules.The discussion identifies the robustness of these mechanisms under other neighborhoods, tie-breaking rules, and update schemes as an open question.Source: §5 · p. 28
  • Prediction for the synchronous, tie-preserving majority rule on the von Neumann neighborhood is settled, while several natural variants remain open.The discussion identifies changing the neighborhood, tie-breaking, and updating scheme as variant dimensions.Source: §5 · pp. 28–29
  • The construction does not immediately extend to the Moore neighborhood, where diagonal interactions change routing possibilities and supporting-pattern stability.The Moore neighborhood includes the four diagonal neighbors in addition to the von Neumann neighborhood.Source: §5 · p. 29
  • For the Toom neighborhood, the freezing case has NC prediction, but prediction for the strict majority rule remains open.The Toom neighborhood gives each cell north and east neighbors.Source: §5 · p. 29
  • The discussion considers uniformly biased tie-breaking and sequential updates, with the latter using a fixed permutation supplied as part of the input.The same update permutation is repeated in every sweep.Source: §5 · p. 29
  • The authors conjecture P-completeness across combinations of the von Neumann or Moore neighborhood, tie-preserving or uniformly biased rules, and synchronous or sequential updates.For sequential updates, the conjecture treats the updating permutation as part of the input.Source: §5 · p. 29
  • Sandpile prediction asks about stabilization outcomes, whether a cell ever topples, or whether a target topples at a prescribed time under synchronous toppling.These formulations retain different aspects of the evolution; timed toppling preserves information not captured by eventual toppling.Source: §5 · pp. 29–30
  • The classical two-dimensional von Neumann sandpile prediction problem remains unresolved, motivating comparison with majority dynamics’ information propagation and signal crossing.The discussion suggests exploring which temporal-encoding mechanisms might adapt to biased tie-breaking, while noting that such parallels may clarify their scope and limitations.Source: §5 · p. 30
Loading 2610.04311v1…