Restart method and exponential acceleration of random 3-SAT instances resolutions: a large deviation analysis of the Davis-Putnam-Loveland-Logemann algorithm

Simona Cocco, Rémi MonassonarXiv 2002 · DOI · arXiv

Abstract

The analysis of the solving complexity of random 3-SAT instances using the Davis-Putnam-Loveland-Logemann (DPLL) algorithm slightly below threshold is presented. While finding a solution for such instances demands exponential effort with high probability, we show that an exponentially small fraction of resolutions require a computation scaling linearly in the size of the instance only. We compute analytically this exponentially small probability of easy resolutions from a large deviation analysis of DPLL with the Generalized Unit Clause search heuristic, and show that the corresponding exponent is smaller (in absolute value) than the growth exponent of the typical resolution time. Our study therefore gives some quantitative basis to heuristic restart solving procedures, and suggests a natural cut-off cost (the size of the instance) for the restart.

Introduction

The 3-SAT problem, a cornerstone of computational complexity theory, involves determining the satisfiability of Boolean formulas. While NP-complete in the general case, random 3-SAT instances exhibit a fascinating phase transition. As the ratio of clauses to variables ($\alpha$) approaches a critical threshold ($\alpha_C \approx 4.3$), instances transition from being easily satisfiable to being almost certainly unsatisfiable and computationally difficult.

This research focuses on the "upper sat phase"—the regime just below the threshold where instances are typically satisfiable but require exponential time for standard algorithms like Davis-Putnam-Loveland-Logemann (DPLL) to solve. In practice, "restarting" a solver with a new random seed has been observed to accelerate finding solutions. This paper provides a rigorous theoretical foundation for this phenomenon using tools from statistical mechanics.

Modeling Solver Trajectories

The authors analyze the DPLL algorithm equipped with the Generalized Unit Clause (GUC) heuristic. The solver's progress is modeled as a dynamical trajectory within a phase diagram defined by clause densities. Specifically, they track the fraction of 3-clauses ($p$) and the ratio of clauses per variable ($\alpha$).

Figure 4: Phase diagram showing the evolution of clause densities ($\alpha$ vs $p$) during the DPLL search. The solid line represents the critical boundary, while dashed lines show trajectories for different initial conditions.

As shown in Figure 4, a "typical" run often enters a "dangerous" region (near point G) where contradictions become frequent, necessitating extensive backtracking and leading to exponential complexity. However, the analysis reveals that some trajectories can "tunnel" through this region, avoiding contradictions and finding a solution in linear time $O(N)$.

Large Deviation Analysis of the "Easy" Tail

The core contribution of this work is the application of large deviation theory to quantify these rare, efficient runs. Instead of focusing on the average-case behavior, the authors calculate the probability of "survival"—the chance that a search branch reaches a solution without backtracking.

They find that even in the hard regime, there is an exponentially small probability, $P \sim 2^{-N\zeta}$, that a solution is found in linear time. Crucially, they demonstrate that the exponent for these rare easy runs ($\zeta$) is significantly smaller than the growth exponent of the typical resolution time ($\omega$). For instance, at $\alpha = 3.5$, they calculate $\zeta \approx 0.011$ compared to $\omega \approx 0.035$.

Empirical Results and Complexity Distributions

To validate their analytical findings, the authors conducted numerical simulations on random 3-SAT instances with variable counts $N$ ranging from 100 to 400.

Figure 5: Normalized distributions of the logarithm of the complexity (divided by size N) for different instance sizes. The shift and narrowing of the distributions illustrate the scaling behavior predicted by large deviation theory.

Figure 5 displays the normalized distribution of the logarithm of complexity. These histograms confirm the existence of a bimodal structure or a significant "easy tail" that scales predictably with $N$. The experimental data matches the theoretical predictions for the $\zeta$ exponent with high accuracy.

The Restart Strategy: From Theory to Practice

The mathematical inequality $\zeta < \omega$ provides the ultimate justification for the restart heuristic. Since the cost of a failed linear-time run is minimal compared to the massive cost of a typical exponential-time run, it is statistically advantageous to "fail fast." By stopping a run after $O(N)$ steps and restarting, the solver essentially samples the distribution until it hits the rare $2^{-N\zeta}$ easy branch.

The practical impact is profound. For $\alpha = 3.5$ and $N = 500$, a standard DPLL run might take a full day. Implementing the restart strategy allowed the authors to solve instances with $N = 1000$ in just 15 minutes. This suggests a "natural cut-off" for restarts: the time required for a single descent in the search tree, which is proportional to the instance size $N$.

Conclusion and Future Directions

By bridging statistical mechanics and computer science, this work transforms a common heuristic into a quantitatively understood strategy. While the current analysis is tailored to the GUC heuristic, it sets a precedent for analyzing more complex modern solvers. Future work may extend this large deviation framework to other combinatorial optimization problems, potentially uncovering similar "easy tails" that can be exploited for exponential acceleration.

Summary updated

Abstract

The analysis of the solving complexity of random 3-SAT instances using the Davis-Putnam-Loveland-Logemann (DPLL) algorithm slightly below threshold is presented. While finding a solution for such instances demands exponential effort with high probability, we show that an exponentially small fraction of resolutions require a computation scaling linearly in the size of the instance only. We compute analytically this exponentially small probability of easy resolutions from a large deviation analysis of DPLL with the Generalized Unit Clause search heuristic, and show that the corresponding exponent is smaller (in absolute value) than the growth exponent of the typical resolution time. Our study therefore gives some quantitative basis to heuristic restart solving procedures, and suggests a natural cut-off cost (the size of the instance) for the restart.
BibTeX
@misc{cocco2002restart,
  author = {Simona Cocco and Rémi Monasson},
  title = {{Restart method and exponential acceleration of random 3-SAT instances resolutions: a large deviation analysis of the Davis-Putnam-Loveland-Logemann algorithm}},
  year = {2002},
  eprint = {cond-mat/0206242},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/cond-mat/0206242},
}
Figure