Landscape analysis of constraint satisfaction problems

We discuss an analysis of constraint satisfaction problems, such as sphere packing, K-SAT, and graph coloring, in terms of an effective energy landscape. Several intriguing geometrical properties of the solution space become in this light familiar in terms of the well-studied ones of rugged (glassy) energy landscapes. A benchmark algorithm naturally suggested by this construction finds solutions in polynomial time up to a point beyond the clustering and in some cases even the thermodynamic transitions. This point has a simple geometric meaning and can be in principle determined with standard statistical mechanical methods, thus pushing the analytic bound up to which problems are guaranteed to be easy. We illustrate this for the graph 3- and 4-coloring problem. For packing problems the present discussion allows to better characterize the $J$-point, proposed as a systematic definition of random close packing, and to place it in the context of other theories of glasses.

Figure 1

(Color online) Potential of soft particles with finite-range interactions. It allows to construct a packing version of the coloring problem (see text).

Figure 2

(Color online) Constructing a pseudoenergy from a constraint satisfaction problem: the regions shown are the satisfied sets at each level of difficulty. The height function is such that at each level the intersection corresponds to a constraint satisfaction problem.

Figure 3

(Color online) Energy vs temperature of a ferromagnet.

Figure 4

(Color online) A sketch of the metastable-state space of the Sherrington-Kirkpatrick model: the gray area in the graph corresponds to a region with an exponential number of metastable states. Inset: complexity along a constant-energy surface line $A$ in terms of temperature $T$ (the same graph would be obtained by plotting in terms of state entropy $\sigma$).

Figure 5

(Color online) The structure of metastable states of the spherical $p$-spin model.

Figure 6

(Color online) A sketch of the organization of states in the Ising $p$-spin model. Inset: complexity in slice $C$; the two vertical lines indicate the dynamic threshold (left-hand side) and the typical configurations (right-hand side), the dashed line symbolizes states that are transparent to the dynamics. The situation in slices $A–E$ have been all found in constraint satisfaction problems for different levels of constraints (see text).

Figure 7

(Color online) The energies $E_d$, $E_K$, $E^{*}$, and $E_o$ for the $p$-spin model as a function of $p$ (from [32]). A simple gradient descent program goes to $E^{*}$ which is beyond $E_d$, $E_K$ for $p<13$.

Figure 8

(Color online) Sketch of the set of solutions in random CSP when the connectivity is increased (adapted from [7, 24]). From left-hand side to right-hand sides, in order of increasing difficulty: (1) easy problem, the whole solution space is connected; (2) a negligible fraction of solutions become disconnected; (3) dynamic transition ${\alpha }_d$, the whole space breaks into dynamically isolated regions, two configurations at random belong to different regions; (4) replica symmetry breaking, Kauzmann point ${\alpha }_K$, the regions become so rare that the probability of two configurations being in the same region is now nonzero; (5) equilibrium rigidity point ${\alpha }^{\text{hard}}$. Typical configurations have frozen variables; (6) best packing, unSat, unCol $({\alpha }_{\text{pack}},{\alpha }_{\mathrm{unsol}},{\alpha }_{\mathrm{uncol}})$, the last configuration satisfying the constraints disappears. Red (dark) and grey regions symbolizes clusters with and without frozen variables, respectively.

Figure 9

(Color online) Adding a link to a tree.

Figure 10

(Color online) Performance of the recursive algorithm for the $q=3,4$ random coloring problem. The time needed to find a proper coloring diverges at connectivity ${\alpha }_{*}<{\alpha }_{\mathrm{uncol}}$ in both cases, but the algorithm is able to find colorings in linear time beyond the clustering ${\alpha }_d$ and Kauzmann ${\alpha }_K$ transitions.

Figure 11

(Color online) Estimate for the asymptotic ${\alpha }^{*}$ of the algorithm. Left-hand side: $q=3$ random coloring problem. Right-hand side: $q=4$ random coloring problem. The two lower families of curves correspond to procedures starting from configurations obtained using the belief propagation algorithm of Ref. 24: the initial advantage seems eventually lost.