  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.
