Bounds on the satisfiability threshold for power law distributed random SAT
Published version
Repository URI
Repository DOI
Change log
Authors
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 averagecase 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 = ϵ(n) clauses, and a power law distribution on the variable occurrences with exponent β. We observe a satisfiability threshold at β≤(2k-1)/(k-1). This threshold is tight in the sense that instances with β ≥ (2k-1)/(k-1)-ϵ for any constant ϵ > 0 are unsatisfiable with high probability (w. h. p.). For β > (2k-1)/(k-1)+ ϵ, 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 β.