Friedrich, Tobias ;
Krohmer, Anton ;
Rothenberger, Ralf ;
Sauerwald, Thomas ;
Sutton, Andrew M.
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 worstcase hardness of SAT lies at the core of computational complexity theory. The averagecase analysis of SAT has triggered the development of sophisticated rigorous and nonrigorous 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, realworld instances often exhibit large fluctuations in variable occurrence. This can be modeled by a scalefree distribution of the variables, which results in distributions closer to industrial SAT instances.
We study random kSAT 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 = (2k1)/(k1). This threshold is tight in the sense that instances with beta <= (2k1)/(k1)epsilon for any constant epsilon > 0 are unsatisfiable with high probability (w.h.p.). For beta >= (2k1)/(k1)+epsilon, the picture is reminiscent of the uniform case: instances are satisfiable w.h.p. for sufficiently small constant clausevariable ratios m/n; they are unsatisfiable above a ratio m/n that depends on beta.
BibTeX  Entry
@InProceedings{friedrich_et_al:LIPIcs:2017:7835,
author = {Tobias Friedrich and Anton Krohmer and Ralf Rothenberger and Thomas Sauerwald and Andrew M. Sutton},
title = {{Bounds on the Satisfiability Threshold for Power Law Distributed Random SAT}},
booktitle = {25th Annual European Symposium on Algorithms (ESA 2017)},
pages = {37:137:15},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959770491},
ISSN = {18688969},
year = {2017},
volume = {87},
editor = {Kirk Pruhs and Christian Sohler},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2017/7835},
URN = {urn:nbn:de:0030drops78356},
doi = {10.4230/LIPIcs.ESA.2017.37},
annote = {Keywords: satisfiability, random structures, random SAT, power law distribution, scalefreeness, phase transitions}
}
2017
Keywords: 

satisfiability, random structures, random SAT, power law distribution, scalefreeness, phase transitions 
Seminar: 

25th Annual European Symposium on Algorithms (ESA 2017)

Issue date: 

2017 
Date of publication: 

2017 