DROPS

Document

DOI: 10.4230/LIPIcs.ESA.2017.37

Bounds on the Satisfiability Threshold for Power Law Distributed Random SAT

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

Published in: LIPIcs, Volume 87, 25th Annual European Symposium on Algorithms (ESA 2017)

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 <= (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.

Cite as

Tobias Friedrich, Anton Krohmer, Ralf Rothenberger, Thomas Sauerwald, and Andrew M. Sutton. Bounds on the Satisfiability Threshold for Power Law Distributed Random SAT. In 25th Annual European Symposium on Algorithms (ESA 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 87, pp. 37:1-37:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{friedrich_et_al:LIPIcs.ESA.2017.37,
  author =	{Friedrich, Tobias and Krohmer, Anton and Rothenberger, Ralf and Sauerwald, Thomas and Sutton, Andrew M.},
  title =	{{Bounds on the Satisfiability Threshold for Power Law Distributed Random SAT}},
  booktitle =	{25th Annual European Symposium on Algorithms (ESA 2017)},
  pages =	{37:1--37:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-049-1},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{87},
  editor =	{Pruhs, Kirk and Sohler, Christian},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2017.37},
  URN =		{urn:nbn:de:0030-drops-78356},
  doi =		{10.4230/LIPIcs.ESA.2017.37},
  annote =	{Keywords: satisfiability, random structures, random SAT, power law distribution, scale-freeness, phase transitions}
}

Search Results

Documents authored by Sutton, Andrew M.

Bounds on the Satisfiability Threshold for Power Law Distributed Random SAT

Abstract

Cite as

Thanks for your feedback!

Could not send message