Revisiting the cavity-method threshold for random 3-SAT

Abstract

A detailed Monte Carlo-study of the satisfiability threshold for random 3-SAT has been undertaken. In combination with a monotonicity assumption we find that the threshold for random 3-SAT satisfies ${\alpha }_3\le 4.262$. If the assumption is correct, this means that the actual threshold value for $k=3$ is lower than that given by the cavity method. In contrast the latter has recently been shown to give the correct value for large $k$. Our result thus indicate that there are distinct behaviors for $k$ above and below some critical $k_c$, and the cavity method may provide a correct mean-field picture for the range above $k_c$.

6 pages, 6 figures

References in corpus (2)

• Gibbs States and the Set of Solutions of Random Constraint Satisfaction Problems
• The set of solutions of random XORSAT formulae

Cited by in corpus (2)

• Convergence of Coupon Collecting Process via Wormald's Differential Equation Method
• Biased random k-SAT