z-logo
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.

This content is not available in your region!

Continue researching here.

Having issues? You can contact us here