Friedrich, Tobias ;
Rothenberger, Ralf
The Satisfiability Threshold for NonUniform Random 2SAT
Abstract
Propositional satisfiability (SAT) is one of the most fundamental problems in computer science. Its worstcase hardness lies at the core of computational complexity theory, for example in the form of NPhardness and the (Strong) Exponential Time Hypothesis. In practice however, SAT instances can often be solved efficiently. This contradicting behavior has spawned interest in the averagecase analysis of SAT and has triggered the development of sophisticated rigorous and nonrigorous 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, realworld instances often exhibit large fluctuations in variable occurrence. This can be modeled by a nonuniform distribution of the variables, which can result in distributions closer to industrial SAT instances.
We study satisfiability thresholds of nonuniform random 2SAT 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 NonUniform Random 2SAT}},
booktitle = {46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)},
pages = {61:161:14},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959771092},
ISSN = {18688969},
year = {2019},
volume = {132},
editor = {Christel Baier and Ioannis Chatzigiannakis and Paola Flocchini and Stefano Leonardi},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2019/10637},
URN = {urn:nbn:de:0030drops106372},
doi = {10.4230/LIPIcs.ICALP.2019.61},
annote = {Keywords: random SAT, satisfiability threshold, sharpness, nonuniform distribution, 2SAT}
}
04.07.2019
Keywords: 

random SAT, satisfiability threshold, sharpness, nonuniform distribution, 2SAT 
Seminar: 

46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)

Issue date: 

2019 
Date of publication: 

04.07.2019 