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.
@cite_40 @cite_4 provided the first asymptotically tight lower bounds on the satisfiability threshold of @math -NAE-SAT and hypergraph 2-colouring, achieving a bound that is roughly equal to the condensation threshold. @cite_38 provides an even stronger bound for hypergraph 2-colouring, extending above the condensation threshold. @cite_29 provides a remarkably strong bound for @math -NAE-SAT - the difference between their upper and lower bounds decreases exponentially with @math .
@cite_38 @cite_40 @cite_29 @cite_4
1610636547 2132891419 2038932251
For many random constraint satisfaction problems such as random satisfiability or random graph or hypergraph coloring, the best current estimates of the threshold for the existence of solutions are based on the first and the second moment method. However, in most cases these techniques do not yield matching upper and lower bounds. Sophisticated but non-rigorous arguments from statistical mechanics have ascribed this discrepancy to the existence of a phase transition called condensation that occurs shortly before the actual threshold for the existence of solutions and that affects the combinatorial nature of the problem (Krzakala, Montanari, Ricci-Tersenghi, Semerjian, Zdeborova: PNAS 2007). In this paper we prove for the first time that a condensation transition exists in a natural random CSP, namely in random hypergraph 2-coloring. Perhaps surprisingly, we find that the second moment method applied to the number of 2-colorings breaks down strictly before the condensation transition. Our proof also yields slightly improved bounds on the threshold for random hypergraph 2-colorability. The best current estimates of the thresholds for the existence of solutions in random constraint satisfaction problems ('CSPs') mostly derive from the first and the second moment method. Yet apart from a very few exceptional cases these methods do not quite yield matching upper and lower bounds. According to deep but non-rigorous arguments from statistical mechanics, this discrepancy is due to a change in the geometry of the set of solutions called condensation that occurs shortly before the actual threshold for the existence of solutions (Krzakala, Montanari, Ricci-Tersenghi, Semerjian, Zdeborova: PNAS 2007). To cope with condensation, physicists have developed a sophisticated but non-rigorous formalism called Survey Propagation (Me-zard, Parisi, Zecchina: Science 2002). This formalism yields precise conjectures on the threshold values of many random CSPs. Here we develop a new Survey Propagation inspired second moment method for the random k-NAESAT problem, which is one of the standard benchmark problems in the theory of random CSPs. This new technique allows us to overcome the barrier posed by condensation rigorously. We prove that the threshold for the existence of solutions in random k-NAESAT is 2k-1ln2-(ln 2 2+1 4)+ek, where |ek| ≤ 2-(1-ok(1))k, thereby verifying the statistical mechanics conjecture for this problem. It is known that random k-CNF formulas have a so-called satisfiability threshold at a density (namely, clause-variable ratio) of roughly 2kln2: at densities slightly below this threshold almost all k-CNF formulas are satisfiable, whereas slightly above this threshold almost no k-CNF formula is satisfiable. In the current work we consider satisfiable random formulas and inspect another parameter—the diameter of the solution space (that is, the maximal Hamming distance between a pair of satisfying assignments). It was previously shown that for all densities up to a density slightly below the satisfiability threshold the diameter is almost surely at least roughly n 2 (and n at much lower densities). At densities very much higher than the satisfiability threshold, the diameter is almost surely zero (a very dense satisfiable formula is expected to have only one satisfying assignment). In this paper we show that for all densities above a density that is slightly above the satisfiability threshold (more precisel...