Markström, Klas & Lundow, Per Håkan | 2019
Journal Version Physical Review E 99
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 α 3 ≤ 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
