Biased random k‐SAT
Joel Larsson, Klas Markström · Random Structures and Algorithms · 2021
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. and positive otherwise—and study how the satisfiability threshold depends on p. For 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 . The former confirms earlier predictions based on numerical studies and heuristic methods from statistical physics.