Introduction
Theoretical research into Boolean Satisfiability (SAT) often relies on the "uniform model" of random k-SAT, where variables are distributed evenly across clauses. However, real-world industrial instances—ranging from hardware verification to software scheduling—frequently exhibit non-uniform, "scale-free" properties. In these cases, a small subset of "power variables" appears in a disproportionately large number of clauses. This paper, presented at AAAI-22, bridges the gap between theory and practice by providing a rigorous mathematical analysis of the Pure Literal Elimination (PLE) heuristic under an arbitrary degree distribution.
The Pure Literal Elimination Heuristic
The PLE rule is a fundamental SAT-solving technique. A literal is "pure" if it appears in a formula with only one polarity (either always $x$ or always $ eg x$). Setting such a variable to satisfy its clauses is always safe and can trigger a cascade: as clauses are removed, other variables may become pure. While simple, PLE is a building block for more complex algorithms like DPLL.
Methodology: Beyond the Uniform Model
To analyze PLE in a more realistic setting, the authors employ the configuration model. Unlike the uniform model, the configuration model allows for any arbitrary distribution of variable degrees. The process involves:
- Assigning a "degree" (total occurrences) to each variable based on a chosen probability distribution.
- Randomly pairing these occurrences to form clauses.
To track the algorithm's progress, the authors utilize Wormald’s Differential Equations Method. This technique treats the discrete, step-by-step execution of the PLE rule as a continuous system of differential equations. By tracking the evolution of variable degrees—specifically, how many variables have $i$ positive and $j$ negative occurrences—the authors derived a precise formula (Theorem 1) to predict the final number of satisfied clauses ($\tau_0$).
Distributional Impact and Key Results
The study tested four distinct degree distributions to represent various data "shapes":
- Subgaussian: Light-tailed, similar to a normal distribution.
- Poisson: Standard exponential decay, often used as a proxy for the uniform model.
- Log-normal: Intermediate decay between exponential and heavy-tailed.
- Zeta: A canonical heavy-tailed (power-law) distribution, mimicking scale-free networks.
The results, illustrated in the figure above, reveal a critical insight: the efficacy of the PLE rule is heavily dictated by the "tail" of the degree distribution.
In light-tailed distributions like the Poisson model, the rule performs exceptionally well at low densities but suffers a sharp "phase transition" or crash once the average degree $\gamma$ exceeds a certain threshold (approximately 5 for 3-SAT). In contrast, the heavy-tailed Zeta distribution shows remarkable resilience. While it satisfies fewer clauses at very low densities, its performance degrades much more gracefully as density increases, remaining useful in regimes where the Poisson-based model would have failed entirely.
Conclusion and Future Directions
This work provides a powerful predictive framework for understanding how basic SAT heuristics behave in non-standard environments. The near-perfect match between the authors' theoretical equations and experimental data validates the use of differential equations for analyzing these stochastic processes.
While the configuration model is a significant step toward realism, it does not yet account for "community structure"—the clustering of variables often seen in industrial problems. Future research may extend this framework to more complex heuristics, such as Unit Clause Elimination, or use it to pinpoint exact satisfiability thresholds for non-uniform models.
Summary updated