Figure 1

Lower and upper Bounds for the $x$-satisfiability threshold ${\alpha }_c(K=8,x)$. The upper curve is obtained by the first moment method. Above this curve there exists no SAT-$x$-pair, w.h.p. The lower curve is obtained by the second moment method. Below this curve there exists a SAT-$x$-pair, w.h.p. For values of $\alpha$ lying between 164.735 and 170.657, these bounds guarantee the existence of a clustering phenomenon. The horizontal line gives an example of this phenomenon for $\alpha =166.1$. We exhibit the successive phases as one varies $x$: $x$-satisfiable regions are represented by a thick solid line, $x$-unsatisfiable regions by a wavy line, and “donot know” regions by a dotted line. The $x$-satisfiable region near $x=0$ corresponds to intracluster pairs, whereas the $x$-satisfiable region around $x=0.5$ corresponds to intercluster pairs. In this example, the intermediate $x$-unsatisfiable region around $x\sim 0.13$ shows the existence of a “gap” between clusters. We recall that the best refined lower and upper bounds for the satisfiability threshold ${\alpha }_c(K=8)$ from 13, 17 are, respectively, 173.253 and 176.596. The cavity prediction is 176.543 [21].Reuse & Permissions