Hiding Quiet Solutions in Random Constraint Satisfaction Problems

We study constraint satisfaction problems on the so-called planted random ensemble. We show that for a certain class of problems, e.g., graph coloring, many of the properties of the usual random ensemble are quantitatively identical in the planted random ensemble. We study the structural phase transitions and the easy-hard-easy pattern in the average computational complexity. We also discuss the finite temperature phase diagram, finding a close connection with the liquid-glass-solid phenomenology.

Figure 1

Phase diagram on the 5-coloring on the planted ensemble. Bottom: Sketches of the clustering. At an average degree $c_d$ the space of solutions shatters into exponentially many clusters, the planted cluster being one of them. Beyond $c_c$ the planted cluster contains more solutions than all the others together. At $c_s$ the last nonplanted cluster disappears. Top: Total entropy $s_{\mathrm{tot}}$ with the subdominant part (dashed). The equilibrium complexity ${\Sigma }_{\mathrm{equilibrium}}$ (logarithm of the number of dominant clusters), the entropy of the nonplanted clusters and critical degrees are taken from 10.

Figure 2

Fraction of variables frozen in their planted colors in 5-coloring of a $N={10}^5$ graph. Data obtained from the BP fixed point when initialized randomly (full triangles) and in the planted configuration (also called the whitening [20], empty circles), compared to the theoretical predictions [10, 13] (full and dashed lines). For $c>c_l=16$ BP converges spontaneously to the planted fixed point. For $c<14.04$ [13] there are no frozen variables in the planted cluster. Inset: Fraction of monochromatic edges versus the number of sweeps of the Walk-COL algorithm [10] in 5-coloring of a purely random and a planted graph, $N={10}^5$. Quiet planting does not seem to affect the computational hardness in the region $c<c_s$.

Figure 3

Finite temperature phase diagram of the planted 5-coloring. At high temperature the liquid is the unique Gibbs state. Below the higher spinodal line $T_1$ a planted (solid) Gibbs state appears, and becomes thermodynamically dominant at the liquid-solid transition. The supercooled liquid state is locally stable until the lower spinodal line $T_2$. The liquid undergoes the usual dynamical and Kauzmann (ideal) glass transitions (data from 10). The thick line depicts the algorithmically hard region, the left boundary being the freezing transition [10]. Inset: Energy versus temperature in Monte Carlo annealing with rate $\delta T={10}^{-2}$, ${10}^{-3}$, ${10}^{-4}$, and ${10}^{-5}$ per sweep for $N=5\times {10}^5$ at $c=20>c_l$. Above $c_l$ a slow enough annealing undergoes a transition towards the planted state.