Theory of Nonequilibrium Local Search on Random Satisfaction Problems

We study local search algorithms to solve instances of the random $k$-satisfiability problem, equivalent to finding (if they exist) zero-energy ground states of statistical models with disorder on random hypergraphs. It is well known that the best such algorithms are akin to nonequilibrium processes in a high-dimensional space. In particular, algorithms known as focused, and which do not obey detailed balance, outperform simulated annealing and related methods in the task of finding the solution to a complex satisfiability problem, that is to find (exactly or approximately) the minimum in a complex energy landscape. A physical question of interest is if the dynamics of these processes can be well predicted by the well-developed theory of equilibrium Gibbs states. While it has been known empirically for some time that this is not the case, an alternative systematic theory that does so has been lacking. In this Letter we introduce such a theory based on the recently developed technique of cavity master equations and test it on the paradigmatic random 3-satisfiability problem. Our theory predicts the qualitative form of the phase boundary between the satisfiable (SAT) and unsatisfiable (UNSAT) region of the phase diagram where the numerics of a focused Metropolis search and cavity master equation cannot be distinguished.

Figure 1

FMS results on 3-SAT instances. Both panels show the number of unsatisfied clauses (system energy) as a function of time, in log-log scale. (Top) Dependency on $\alpha$ of FMS behavior. There is a transition between when a FMS works (finds a solution in integration time considered), and when it does not. These calculations were done with $\eta =0.45$ and system size $N={10}^5$. Averages over 500 different histories were made for each $\alpha$. (Bottom) The FMS’s dependency on $N$ for $\eta =0.45$ and $\alpha =3.6<{\alpha }_c$. Lines are a guide to the eyes.

Figure 2

CME results on 3-SAT instances. Both figures show the number of unsatisfied clauses (system energy) as a function of time, in log-log scale for different values of $\alpha$. (Top) Comparison between the CME (lines) and FMS (points) with $\eta =0.4$ and system size $N=2000$. (Bottom) Comparison between the CME (lines) and FMS (points) for $\eta =0.65$ and $N=5000$. There is a transition between a phase in which solutions of the CME reaches zero energy in finite time, and a phase where they do not. In the region where frustration increases, i.e., for high $\alpha$, the CME will not reach zero energy even when the FMS typically is able to find solutions. In this region, long range fluctuations in time and/or in the graph are important.

Figure 3

Comparison between the phase diagrams of a focused Metropolis search (FMS) and cavity master equation (CME). The phase boundary of a FMS was obtained by running 100 instances of the problem at different $\alpha$ for a time $10^5·N$ and determining at which value of $\alpha$ half of them find a solution in the given time (filled-in circles). Convergence is slower in the lower “descending” branch of a FMS. The phase diagram of the CME was found by integrating the CME for 24 instances (thick-line circles) or at least 4 instances (thin-line circles) of the problem at different $\alpha$. Results for each $\alpha$ were placed in log-log plots as the ones of Fig. 2 and it was determined for which value of $\alpha$ half of them did not converge to zero. We used $N=5000$ for $\eta \ge 0.65$, $N=2000$ for $0.4\le \eta \le 0.65$, and $N=500$ for $\eta <0.4$.