Biased random k‐SAT. Issue 2 (16th February 2021)

• Record Type: Journal Article
• Authors: Larsson, Joel; Markström, Klas
• Is Part Of: Random structures & algorithms. Volume 59:Issue 2(2021)
• Page Start: 238
• Page End: 266
• Publication Date: 2021-02-16
• Subjects: combinatorial probability -- phase transition -- random k‐SAT -- random constraint satisfaction problem; Random graphs -- Periodicals; Mathematical analysis -- Periodicals; 519
• DOI: 10.1002/rsa.20996
• Languages: English
• ISSNs: 1042-9832

Abstract

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.