Counting and Hardness-of-Finding Fixed Points in Cellular Automata on Random Graphs

Cédric Koller, Freya Behrens, Lenka Zdeborová

Abstract: We study the fixed points of outer-totalistic cellular automata on sparse random regular graphs. These can be seen as constraint satisfaction problems, where each variable must adhere to the same local constraint, which depends solely on its state and the total number of its neighbors in each possible state. Examples of this setting include classical problems such as independent sets or assortative/dissasortative partitions. We analyse the existence and number of fixed points in the large system limit using the cavity method, under both the replica symmetric (RS) and one-step replica symmetry breaking (1RSB) assumption. This method allows us to characterize the structure of the space of solutions, in particular, if the solutions are clustered and whether the clusters contain frozen variables. This last property is conjectured to be linked to the typical algorithmic hardness of the problem. We bring experimental evidence for this claim by studying the performance of the belief-propagation reinforcement algorithm, a message-passing-based solver for these constraint satisfaction problems.

Introduction

Cellular Automata (CAs) are discrete dynamical systems typically studied on regular grids for their ability to generate complex global behaviors from simple local rules. This research shifts the focus to Random Regular Graphs (RRGs), leveraging tools from the statistical physics of disordered systems to analyze the large system limit. The primary objective is to characterize the fixed points of outer-totalistic CAs, treating them as solutions to Constraint Satisfaction Problems (CSPs). By mapping the landscape of these solutions, the authors aim to identify the structural properties that dictate computational hardness.

Methodology

The study employs the cavity method to analyze the existence and distribution of fixed points. This involves several theoretical and algorithmic approaches, including Replica Symmetry (RS) and 1-step Replica Symmetry Breaking (1RSB) frameworks. These describe the organization of the solution space, ranging from a single connected component to many disconnected clusters.

Factor graph representation of cellular automata fixed points mapping local rules to constraints.

To solve these systems numerically, the authors use Belief Propagation (BP) to estimate solution counts and BP-Reinforcement as an algorithmic solver. The local constraints of the CA are mapped onto a factor graph, as shown above, allowing for the application of these message-passing algorithms.

The Solution Space Landscape

A central theme of the paper is the classification of solution spaces into different phases. The authors distinguish between RS, where solutions form a single cluster, and 1RSB phases (dynamical and static), where the space shatters into many clusters.

Illustration of solution space phases (RS, d1RSB, s1RSB) and the complexity Σ as a function of density φ_i.

The complexity Σ, or configurational entropy, measures the number of clusters. As illustrated in the figure above, the transition to a state where Σ vanishes or where clusters contain "frozen" variables—nodes that must take the same value in every solution within a cluster—often marks the point where finding solutions becomes algorithmically difficult.

Results and Algorithmic Hardness

The researchers analyzed all 136 non-equivalent rules for d=3 and a subset for d=4. Key findings include:

  • Freezing and Hardness: There is a strong correlation between the presence of frozen variables and the failure of solvers. Rules in the RS phase were solved with a 100% success rate, whereas those with frozen clusters (e.g., rule 1010) saw success rates drop to 0-10%.
  • Atypical Solutions: In certain hard d=4 cases, BP-Reinforcement succeeded by finding "atypical" solutions—rare configurations in wide, flat regions of the landscape—despite the dominance of frozen, unreachable clusters.
  • Entropy Matching: For most d=3 rules, the quenched free entropy matches the annealed average, indicating a relatively simple landscape, with only a few exceptions exhibiting 1RSB behavior.

Conclusion

This work demonstrates that the geometric structure of the solution space, particularly the freezing transition, is a reliable predictor of algorithmic performance in finding CA fixed points. Future research may extend these findings to multi-state alphabets, more complex graph topologies, and the temporal dynamics leading to these fixed points.

Summary updated

Abstract

We study the fixed points of outer-totalistic cellular automata on sparse random regular graphs. These can be seen as constraint satisfaction problems, where each variable must adhere to the same local constraint, which depends solely on its state and the total number of its neighbors in each possible state. Examples of this setting include classical problems such as independent sets or assortative/dissasortative partitions. We analyse the existence and number of fixed points in the large system limit using the cavity method, under both the replica symmetric (RS) and one-step replica symmetry breaking (1RSB) assumption. This method allows us to characterize the structure of the space of solutions, in particular, if the solutions are clustered and whether the clusters contain frozen variables. This last property is conjectured to be linked to the typical algorithmic hardness of the problem. We bring experimental evidence for this claim by studying the performance of the belief-propagation reinforcement algorithm, a message-passing-based solver for these constraint satisfaction problems.
BibTeX
@article{koller2024counting,
  author = {Cédric Koller and Freya Behrens and Lenka Zdeborová},
  title = {{Counting and Hardness-of-Finding Fixed Points in Cellular Automata on Random Graphs}},
  journal = {Journal of Physics A Mathematical and Theoretical},
  year = {2024},
  doi = {10.1088/1751-8121/ad8797},
}
Figure