On the Empirical Time Complexity of Random 3-SAT at the Phase Transition

Zongxu Mu, Holger H. HoosIJCAI 2015

Abstract

This study investigates the empirical scaling behavior of SAT solvers on random 3-SAT instances at the solubility phase transition. By applying a rigorous statistical methodology involving parametric modeling and bootstrapping, we distinguish between exponential and polynomial scaling. Our findings reveal a significant divergence: while complete DPLL-based solvers scale exponentially as expected, incomplete Stochastic Local Search (SLS) solvers exhibit polynomial scaling ($O(n^3)$). This suggests that random 3-SAT at the phase transition may not represent the true worst-case complexity for all algorithmic approaches.

Introduction

Propositional satisfiability (SAT) is a fundamental NP-complete problem. While theoretical worst-case complexity is exponential, practical performance varies widely. For decades, random 3-SAT instances at the phase transition—where approximately 50% of instances are satisfiable—have served as the benchmark for "hard" instances. However, the exact nature of how solver time scales with the number of variables ($n$) at this point has remained a subject of debate. This paper aims to resolve this by determining whether scaling is truly exponential or polynomial using a rigorous empirical scaling analysis.

Methodology

The authors employ a multi-stage approach to analyze scaling:

  1. Phase Transition Refinement: Initial analysis showed that existing models for locating the phase transition (e.g., Crawford & Auton, 1996) lose accuracy for $n > 300$. A new 4-parameter model was developed to better align with statistical physics predictions.
  2. Parametric Modeling: Median running times were fitted against two competing models:
  3. Exponential: $Time(n) = a \cdot b^n$
  4. Polynomial: $Time(n) = a \cdot n^b$
  5. Bootstrapping and Extrapolation: Models were trained on "support data" (smaller $n$) and validated against "challenge data" (larger $n$). 1000 bootstrap samples were used to generate 95% confidence intervals, allowing for the statistical rejection of models that failed to predict performance on unseen instance sizes.

Empirical Scaling Analysis

The study evaluated two classes of solvers: Stochastic Local Search (SLS) solvers (WalkSAT/SKC, BalancedZ, probSAT) and complete DPLL solvers (kcnfs, march_hi, march_br).

Scaling of SLS solvers (WalkSAT/SKC) at the phase transition. The polynomial model provides a significantly better fit for the challenge data than the exponential model.

For SLS solvers, the results were unexpected. As shown in Figure 2, the polynomial model fits the challenge data far more accurately than the exponential model. In fact, exponential models were rejected with 95% confidence across all tested SLS solvers, which consistently demonstrated polynomial scaling with an exponent of approximately 3.

Scaling of DPLL solvers (march_hi) at the phase transition. Unlike SLS solvers, complete solvers exhibit clear exponential growth in median CPU time.

In contrast, DPLL solvers followed the expected theoretical path. As illustrated in Figure 3 for the march_hi solver, the median CPU time grows exponentially. For these solvers, polynomial models were rejected with 95% confidence, with the data supporting an exponential base of approximately 1.03.

Key Results and Discussion

The primary discovery is the "SLS Surprise": local search solvers scale polynomially at the phase transition. This implies that the inherent difficulty of these "hard" random instances is qualitatively different for local search compared to systematic search.

Furthermore, for DPLL solvers, the scaling behavior on satisfiable versus unsatisfiable instances was found to be nearly identical, differing only by a constant factor. This suggests that the rate of growth in computational hardness is independent of the instance's satisfiability.

Conclusion

The findings suggest that random 3-SAT at the phase transition might not be the ideal proxy for the worst-case difficulty of NP-hard problems, given that simple local search algorithms can solve them with polynomial scaling. While this study provides a rigorous benchmark for random instances, future work should extend this methodology to structured, real-world SAT instances where polynomial scaling may not hold. The authors propose that this resampling methodology could be a powerful tool for re-evaluating the empirical complexity of other NP-hard problems.

Summary updated

BibTeX
@inproceedings{mu2015empirical,
  author = {Zongxu Mu and Holger H. Hoos},
  title = {{On the Empirical Time Complexity of Random 3-SAT at the Phase Transition}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2015},
}
Figure