2026-07-21T19:22:39Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:7835 2024-03-12T11:58:16Z ddc:004 open_access

Bounds on the Satisfiability Threshold for Power Law Distributed Random SAT Friedrich, Tobias Krohmer, Anton Rothenberger, Ralf Sauerwald, Thomas Sutton, Andrew M. satisfiability random structures random SAT power law distribution scale-freeness phase transitions 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 <= (2k-1)/(k-1)-epsilon for any constant epsilon > 0 are unsatisfiable with high probability (w.h.p.). For beta >= (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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Tobias Friedrich and Anton Krohmer and Ralf Rothenberger and Thomas Sauerwald and Andrew M. Sutton 2017 Is Part Of LIPIcs, Volume 87, 25th Annual European Symposium on Algorithms (ESA 2017) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ESA.2017.37 urn:nbn:de:0030-drops-78356 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2017.37 eng https://creativecommons.org/licenses/by/3.0/legalcode