License
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ICALP.2019.61
URN: urn:nbn:de:0030-drops-106372
URL: http://drops.dagstuhl.de/opus/volltexte/2019/10637/
Go to the corresponding LIPIcs Volume Portal


Friedrich, Tobias ; Rothenberger, Ralf

The Satisfiability Threshold for Non-Uniform Random 2-SAT

pdf-format:
LIPIcs-ICALP-2019-61.pdf (0.5 MB)


Abstract

Propositional satisfiability (SAT) is one of the most fundamental problems in computer science. Its worst-case hardness lies at the core of computational complexity theory, for example in the form of NP-hardness and the (Strong) Exponential Time Hypothesis. In practice however, SAT instances can often be solved efficiently. This contradicting behavior has spawned interest in the average-case analysis of SAT and has triggered the development of sophisticated rigorous and non-rigorous techniques for analyzing random structures. Despite a long line of research and substantial progress, most 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 non-uniform distribution of the variables, which can result in distributions closer to industrial SAT instances. We study satisfiability thresholds of non-uniform random 2-SAT with n variables and m clauses and with an arbitrary probability distribution (p_i)_{i in[n]} with p_1 >=slant p_2 >=slant ... >=slant p_n>0 over the n variables. We show for p_{1}^2=Theta (sum_{i=1}^n p_i^2) that the asymptotic satisfiability threshold is at {m=Theta ((1-{sum_{i=1}^n p_i^2})/(p_1 * (sum_{i=2}^n p_i^2)^{1/2}))} and that it is coarse. For p_{1}^2=o (sum_{i=1}^n p_i^2) we show that there is a sharp satisfiability threshold at m=(sum_{i=1}^n p_i^2)^{-1}. This result generalizes the seminal works by Chvatal and Reed [FOCS 1992] and by Goerdt [JCSS 1996].

BibTeX - Entry

@InProceedings{friedrich_et_al:LIPIcs:2019:10637,
  author =	{Tobias Friedrich and Ralf Rothenberger},
  title =	{{The Satisfiability Threshold for Non-Uniform Random 2-SAT}},
  booktitle =	{46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)},
  pages =	{61:1--61:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-109-2},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{132},
  editor =	{Christel Baier and Ioannis Chatzigiannakis and Paola Flocchini and Stefano Leonardi},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2019/10637},
  URN =		{urn:nbn:de:0030-drops-106372},
  doi =		{10.4230/LIPIcs.ICALP.2019.61},
  annote =	{Keywords: random SAT, satisfiability threshold, sharpness, non-uniform distribution, 2-SAT}
}

Keywords: random SAT, satisfiability threshold, sharpness, non-uniform distribution, 2-SAT
Seminar: 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)
Issue Date: 2019
Date of publication: 08.07.2019


DROPS-Home | Imprint | Privacy Published by LZI