We found a match
Your institution may have rights to this item. Sign in to continue.
- Title
Biased random k-SAT.
- Authors
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.
- Subjects
STATISTICAL physics; HEURISTIC; RANDOM sets; BOOLEAN functions; CONSTRAINT satisfaction; CUBES
- Publication
Random Structures & Algorithms, 2021, Vol 59, Issue 2, p238
- ISSN
1042-9832
- Publication type
Article
- DOI
10.1002/rsa.20996