Biased random k‐SAT. Issue 2 (16th February 2021) - Larsson, Joel; Markström, Klas
Abstract: 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 2 and positive otherwise—and study how the satisfiability threshold depends on p . For p < 1 2 this 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 or 1 2 . The former confirms earlier predictions based on numerical studies and heuristic methods from statistical physics.