Abstract: We report results from large-scale experiments in satisfiability testing. As has been observed by others, testing the satisfiability of random formulas often appears surprisingly easy. Here we show that by using the right distribution of instances, and appropriate parameter values, it is possible to generate random formulas that are hard, that is, for which satisfiability testing is quite difficult. Our results provide a benchmark for the evaluation of satisfiability-testing procedures.
Introduction
In the early 1990s, the artificial intelligence community faced a paradox regarding NP-hard problems like Boolean Satisfiability (SAT). While theoretically difficult in the worst case, empirical studies often found that random SAT instances were solved with surprising ease. Some researchers even suggested that SAT might be solvable in $O(n^2)$ time on average. Mitchell, Selman, and Levesque (1992) challenged these views, arguing that such claims were artifacts of "easy" problem distributions. They sought to identify the specific parameters that generate truly difficult random instances to serve as a rigorous stress test for search algorithms.
Experimental Framework
The researchers focused on the Davis-Putnam (DP) procedure, a foundational backtracking search algorithm utilizing unit propagation. To measure computational difficulty, they tracked the number of recursive calls required to determine satisfiability.
They primarily utilized the Fixed Clause-Length Model (Random 3-SAT), where every clause contains exactly three literals. By systematically varying the number of variables ($N$) and the number of clauses ($L$), they analyzed how the ratio $L/N$ influenced search complexity. To ensure statistical robustness, they sampled 500 instances for each data point and reported the median number of DP calls, preventing outliers from skewing the results.
The Easy-Hard-Easy Phenomenon
The study revealed a distinct "easy-hard-easy" pattern in computational cost governed by the clause-to-variable ratio:
- Under-constrained (Low $L/N$): Formulas have many satisfying assignments, allowing search algorithms to find solutions almost immediately.
- Over-constrained (High $L/N$): Formulas are almost certainly unsatisfiable. The high density of constraints allows the algorithm to quickly identify contradictions and terminate.
- The Critical Zone: The hardest problems reside in a narrow transition region where the formula is neither obviously solvable nor obviously impossible.
As shown in Figure 1, for a 50-variable 3-SAT problem, the median number of DP calls spikes from near-zero at a ratio of 3.0 to nearly 4,000 calls at the critical ratio, before dropping significantly as the ratio increases toward 8.0.
The Phase Transition
The authors discovered that the peak of computational difficulty coincides with a "phase transition" in the probability of satisfiability. For 3-SAT, this transition occurs at a ratio ($L/N$) of approximately 4.3. At this "magic ratio," a random formula has roughly a 50% chance of being satisfiable.
Figure 2 illustrates this transition. As the ratio increases, the probability of finding a satisfying assignment drops precipitously. The point where this probability is 0.5 marks the region where search algorithms must work the hardest to prove either satisfiability or unsatisfiability.
Conclusion and Implications
This research fundamentally changed how SAT solvers are benchmarked. It demonstrated that problem size alone is a poor predictor of difficulty; a 250-variable problem at the critical ratio can be far more difficult than a 1,000-variable problem far from it. By identifying the 4.3 ratio, the authors provided a "dial" for researchers to generate problems of predictable, high difficulty. While the study focused on the DP procedure, the authors conjectured that this hardness landscape is a fundamental property of the SAT problem itself, rather than a specific algorithm, a hypothesis that has largely been validated by subsequent decades of research.
Summary updated