Bounds on the satisfiability threshold for power law distributed random SAT

Tobias Friedrich, Anton Krohmer, Ralf Rothenberger, Thomas Sauerwald, Andrew M. Sutton

Research output: Chapter in Book/Report/Conference proceedingConference contribution

2 Scopus citations

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 β.

Original languageEnglish (US)
Title of host publication25th European Symposium on Algorithms, ESA 2017
EditorsChristian Sohler, Christian Sohler, Kirk Pruhs
PublisherSchloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
ISBN (Electronic)9783959770491
DOIs
StatePublished - Sep 1 2017
Event25th European Symposium on Algorithms, ESA 2017 - Vienna, Austria
Duration: Sep 4 2017Sep 6 2017

Publication series

NameLeibniz International Proceedings in Informatics, LIPIcs
Volume87
ISSN (Print)1868-8969

Other

Other25th European Symposium on Algorithms, ESA 2017
CountryAustria
CityVienna
Period9/4/179/6/17

Keywords

  • Phase transitions
  • Power law distribution
  • Random SAT
  • Random structures
  • Satisfiability
  • Scale-freeness

Fingerprint Dive into the research topics of 'Bounds on the satisfiability threshold for power law distributed random SAT'. Together they form a unique fingerprint.

Cite this