We determine the exact freezing threshold, r^f, for a family of models of random boolean constraint satisfaction problems, including NAE-SAT and hypergraph 2-colouring, when the constraint size is sufficiently large. If the constraint-density of a random CSP, F, in our family is greater than r^f then for almost every solution of F, a linear number of variables are frozen, meaning that their colours cannot be changed by a sequence of alterations in which we change o(n) variables at a time, always switching to another solution. If the constraint-density is less than r^f, then almost every solution has o(n) frozen variables. Freezing is a key part of the clustering phenomenon that is hypothesized by non-rigorous techniques from statistical physics. The understanding of clustering has led to the development of advanced heuristics such as Survey Propogation. It has been suggested that the freezing threshold is a precise algorithmic barrier: that for densities below r^f the random CSPs can be solved using very simple algorithms, while for densities above r^f one requires more sophisticated techniques in order to deal with frozen clusters.
Achlioptas and Ricci-Tersenghi @cite_17 were the first to rigorously prove that freezing occurs in a random CSP. They studied random @math -SAT and showed that for @math , for a wide range of edge-densities below the satisfiability threshold and for every satisfying assignment @math , the vast majority of variables are 1-frozen w.r.t @math . They did so by stripping down to the *-core, which inspired us to do the same here. One difference between their approach and ours is that the variables of the *-core are 1-frozen by definition, whereas much of the work in this paper is devoted to proving that, for our models, they are in fact @math -frozen. We expect that our techniques should be able to prove that the 1-frozen variables established in @cite_17 are, indeed, @math -frozen.
@cite_17
1980276492
For a number of random constraint satisfaction problems, such as random k-SAT and random graph hypergraph coloring, there are very good estimates of the largest constraint density for which solutions exist. Yet, all known polynomial-time algorithms for these problems fail to find solutions even at much lower densities. To understand the origin of this gap we study how the structure of the space of solutions evolves in such problems as constraints are added. In particular, we prove that much before solutions disappear, they organize into an exponential number of clusters, each of which is relatively small and far apart from all other clusters. Moreover, inside each cluster most variables are frozen, i.e., take only one value. The existence of such frozen variables gives a satisfying intuitive explanation for the failure of the polynomial-time algorithms analyzed so far. At the same time, our results establish rigorously one of the two main hypotheses underlying Survey Propagation, a heuristic introduced by physicists in recent years that appears to perform extraordinarily well on random constraint satisfaction problems.