Bounds on the Satisfiability Threshold for Power Law Distributed Random SAT

Abstract

Propositional satisfiability (SAT) is one of the most fundamental problems in computer science. The worst-case hardness of SAT lies at the core of computational complexity theory. The average-case analysis of SAT has triggered the development of sophisticated rigorous and non-rigorous techniques for analyzing random structures. Despite a long line of research and substantial progress, nearly all theoretical work on random SAT assumes a uniform distribution on the variables. In contrast, real-world instances often exhibit large fluctuations in variable occurrence. This can be modeled by a scale-free distribution of the variables, which results in distributions closer to industrial SAT instances. We study random k-SAT on n variables, $m=\Theta (n)$ clauses, and a power law distribution on the variable occurrences with exponent $\beta$. We observe a satisfiability threshold at $\beta =(2k-1)/(k-1)$. This threshold is tight in the sense that instances with $\beta \le (2k-1)/(k-1)-\epsilon$ for any constant $\epsilon >0$ are unsatisfiable with high probability (w.h.p.). For $\beta \ge (2k-1)/(k-1)+\epsilon$, the picture is reminiscent of the uniform case: instances are satisfiable w.h.p. for sufficiently small constant clause-variable ratios $m/n$; they are unsatisfiable above a ratio $m/n$ that depends on $\beta$.

17 pages