We study a system of $y=2$ coupled copies of a well-known constraint
satisfaction problem (random hypergraph bicoloring) to examine how the
ferromagnetic coupling between the copies affects the properties of the
solution space. We solve the replicated model by applying the cavity method to
the supervariables taking $2^y$ values. Our results show that a coupling of
strength $\gamma$ between the copies decreases the clustering threshold
$\alpha_d(\gamma)$, at which typical solutions shatters into disconnected
components, therefore preventing numerical methods such as Monte Carlo Markov
Chains from reaching equilibrium in polynomial time. This result needs to be
reconciled with the observation that, in models with coupled copies, denser
regions of the solution space should be more accessible. Additionally, we
observe a change in the nature of the clustering phase transition, from
discontinuous to continuous, in a wide $\gamma$ range. We investigate how the
coupling affects the behavior of the Belief Propagation (BP) algorithm on
finite-size instances and find that BP convergence is significantly impacted by
the continuous transition. These results highlight the importance of better
understanding algorithmic performance at the clustering transition, and call
for a further exploration into the optimal use of re-weighting strategies
designed to enhance algorithmic performances.

Dieser Artikel untersucht Zeitreisen und deren Auswirkungen.

PDF herunterladen: