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$).
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 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