Revisiting the cavity-method threshold for random 3-SAT.
basic_science · Level V
Where this comes from
- Record sourced from PubMed, PMID 30934345.
- Also identified by DOI 10.1103/PhysRevE.99.022106.
- No licence information is recorded for this record.
- Because redistribution is not established, this page shows the abstract only. Follow the links below for the full text.
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 α_{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}.