Abstract
A large deviation analysis of the solving complexity of random 3-satisfiability instances slightly below threshold is presented. While finding a solution for such instances demands an 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. This exponentially small probability of easy resolutions is analytically calculated, and the corresponding exponent is shown to be smaller (in absolute value) than the growth exponent of the typical resolution time. Our study therefore gives some theoretical basis to heuristic stop-and-restart solving procedures, and suggests a natural cutoff (the size of the instance) for the restart.
Introduction
The 3-Satisfiability (3-SAT) problem—determining if a set of logical constraints on boolean variables can be satisfied—is a cornerstone of computational complexity. For random 3-SAT instances, the difficulty is governed by the ratio of clauses ($M$) to variables ($N$), denoted as $\alpha$. It is well-established that a phase transition occurs: for $\alpha < 3.003$, problems are generally easy (polynomial time); for $3.003 < \alpha < 4.3$, they are satisfiable but typically require exponential time; and above $\alpha \approx 4.3$, they become almost certainly unsatisfiable.
This paper, published in 2002 by Simona Cocco and Rémi Monasson, investigates the "Hard Regime" ($3.003 < \alpha < 4.3$). While the typical case is exponential, the authors explore the existence of "large deviations"—rare instances where a standard solver like the DPLL (Davis-Putnam-Loveland-Logemann) algorithm finds a solution in linear time.
The Bimodal Distribution of Complexity
The core finding is that the distribution of solving times is not a simple unimodal curve. Instead, it exhibits a bimodal structure. There is a "fast" peak corresponding to linear-time resolutions and a "slow" bump representing the typical exponential-time resolutions.
As the problem size $N$ increases, the "slow" bump shifts and dominates the average behavior. However, the "fast" peak never completely vanishes; it merely becomes exponentially rare. These "lucky" trajectories occur when the solver finds a solution on the very first branch of the search tree without significant backtracking.
Theoretical Foundation for Restarts
To quantify this, the authors define two critical exponents:
- $\omega$: The growth rate of the typical resolution time.
- $\zeta$: The decay rate of the probability of a linear resolution.
By mapping the search process onto a physical phase diagram using tools from statistical physics, the authors derived a partial differential equation to calculate these exponents.
Crucially, the analysis reveals that $\zeta < \omega$. This inequality provides the mathematical justification for "stop-and-restart" (S&R) strategies. Because the cost of missing a "lucky" run (governed by $\zeta$) is lower than the cost of completing a "typical" hard run (governed by $\omega$), it is more efficient to quit a long-running search and try again with a different random seed.
Practical Results and Implementation
The theoretical insights translate into massive performance gains. For $\alpha = 3.5$, the typical complexity grows as $2^{0.035N}$. Using an S&R strategy with a linear-time cutoff (specifically, a search tree size proportional to $N$), the complexity scales as $N \cdot 2^{0.011N}$.
In practical tests:
- A standard DPLL solver required one day to solve a 500-variable instance at $\alpha = 3.5$.
- The S&R strategy solved a 1000-variable instance in just 15 minutes on the same hardware.
The authors suggest that the "natural" cutoff for a restart is the size of the instance ($N$). If the search tree exceeds $N$ nodes, the solver has likely entered the "slow" regime, and a restart is statistically optimal.
Limitations
While powerful, this analysis is specifically tailored to random 3-SAT instances. Real-world problems (e.g., in hardware verification) often possess internal structures that may alter these probability distributions. Furthermore, the specific values of $\zeta$ and $\omega$ depend on the heuristic used by the solver (such as the GUC rule). As $\alpha$ approaches the satisfiability threshold ($\alpha_C \approx 4.3$), the "lucky" runs become increasingly rare, potentially diminishing the advantage of the restart strategy.
Summary updated