Balanced K-satisfiability and biased random K-satisfiability on trees

摘要

We study and solve some variations of the random K-satisfiability (K-SAT) problem—balanced K-SAT andnbiased random K-SAT—on a regular tree, using techniques we have developed earlier. In both these problems asnwell as variations of these that we have looked at, we find that the transition from the satisfiable to the unsatisfiablenregime obtained on the Bethe lattice matches the exact threshold for the same model on a random graph fornK = 2 and is very close to the numerical value obtained for K = 3. For higher K, it deviates from the numericalnestimates of the solvability threshold on random graphs but is very close to the dynamical one-step-replicasymmetry-nbreaking threshold as obtained from the first nontrivial fixed point of the survey propagation algorithm.