Satisfiability and Algorithms for Non-uniform Random k-SAT

Oleksii Omelchenko, Andrei BulatovAAAI 2021 · DOI

Introduction

The Boolean Satisfiability problem (SAT) is a cornerstone of computer science, serving as a fundamental NP-complete benchmark. A curious paradox exists in the field: while small, uniformly random SAT instances are often computationally intractable, massive "industrial" instances with millions of variables are solved routinely. This discrepancy suggests that real-world problems possess structural properties absent in uniform models.

One leading hypothesis is that industrial instances feature a non-uniform degree distribution, where a few "hub" variables appear frequently while most appear rarely—a characteristic of power-law distributions. This paper investigates the Configuration Model for random $k$-SAT to determine if this structure explains solver efficiency and to identify the mathematical "phase transition" between satisfiability and unsatisfiability in these models.

Methodology

The researchers employed the Configuration Model to generate synthetic formulas through a four-step process:

  1. Degree Sampling: Variable degrees are sampled from a power-law (Zeta) distribution.
  2. Cloning: Variables are cloned according to their assigned degrees.
  3. Matching: Clones are randomly partitioned into groups of $k$ to form clauses.
  4. Polarity: Literals are randomly negated with 50% probability.

To analyze these formulas, the authors introduced Algorithm 2 (ISSAT), a "myopic" algorithm that reduces $k$-SAT to 2-SAT by selecting the two lowest-degree literals in each clause. Because 2-SAT is solvable in linear time, a satisfiable reduced formula guarantees the satisfiability of the original $k$-SAT instance.

Key Insights: Why Solvers Excel on Non-uniform Instances

A primary finding is that modern SAT solvers (e.g., CryptoMiniSAT) benefit significantly from variable degree variability. In uniform or $d$-regular models, all variables appear identical to the solver's heuristics, leading to exponential branching. In power-law models, high-degree "hubs" and low-degree "leaves" provide strong signals for branching decisions.

Figure 3: Solver branching complexity across different degree distributions. Zeta-distributed instances show significantly lower branching compared to uniform and d-regular models.

As shown in the experimental data, the number of branches explored by solvers scales almost linearly with the number of variables for heavy-tailed distributions, whereas complexity remains exponential for uniform counterparts.

Empirical Results and Phase Transitions

The study established both theoretical bounds and empirical thresholds for satisfiability. Theoretically, if the power-law parameter $\alpha < k/(k-1)$, the formula is almost certainly unsatisfiable due to the emergence of a dense, contradictory "core."

Figure 2: Empirical satisfiability and ISSAT algorithm success probability for 3-CNF instances. The transition occurs near $\beta \approx 2.5$.

Empirical validation for $k=3$ shows a sharp transition from satisfiable to unsatisfiable near $\beta \approx 2.5$. The gap between the necessary and sufficient conditions identified by the authors is remarkably narrow—only 4.6% for $k=3$, shrinking to less than 1% as $k$ increases.

Conclusion and Future Directions

While degree distribution is a critical factor in the tractability of "industrial-like" SAT instances, it is not the sole contributor. Other structural features, such as community structure and low treewidth, likely play complementary roles. Future research will focus on narrowing the theoretical gap between satisfiability conditions and exploring the interplay between power-law distributions and other structural properties like "backdoor" variables.

Summary updated

BibTeX
@inproceedings{omelchenko2021satisfiability,
  author = {Oleksii Omelchenko and Andrei Bulatov},
  title = {{Satisfiability and Algorithms for Non-uniform Random k-SAT}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2021},
  doi = {10.1609/aaai.v35i5.16507},
}
Figure