Premium
Biased random k ‐SAT
Author(s) -
Larsson Joel,
Markström Klas
Publication year - 2021
Publication title -
random structures and algorithms
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.314
H-Index - 69
eISSN - 1098-2418
pISSN - 1042-9832
DOI - 10.1002/rsa.20996
Subject(s) - mathematics , combinatorics , maximum satisfiability problem , boolean satisfiability problem , satisfiability , random variable , heuristic , set (abstract data type) , boolean data type , discrete mathematics , boolean function , computer science , statistics , mathematical optimization , programming language
The basic random k ‐SAT problem is: given a set of n Boolean variables, and m clauses of size k picked uniformly at random from the set of all such clauses on our variables, is the conjunction of these clauses satisfiable? Here we consider a variation of this problem where there is a bias towards variables occurring positive—that is, variables occur negated w.p. 0 < p < 1 2and positive otherwise—and study how the satisfiability threshold depends on p . For p < 1 2this model breaks many of the symmetries of the original random k ‐SAT problem, for example, the distribution of satisfying assignments in the Boolean cube is no longer uniform. For any fixed k , we find the asymptotics of the threshold as p approaches 0 or1 2. The former confirms earlier predictions based on numerical studies and heuristic methods from statistical physics.