The number of satisfying assignments of random 2‐SAT formulas. Issue 4 (17th January 2021)

• Record Type: Journal Article
• Authors: Achlioptas, Dimitris; Coja‐Oghlan, Amin; Hahn‐Klimroth, Max; Lee, Joon; Müller, Noëla; Penschuck, Manuel; Zhou, Guangyan
• Is Part Of: Random structures & algorithms. Volume 58:Issue 4(2021)
• Page Start: 609
• Page End: 647
• Publication Date: 2021-01-17
• Subjects: 2‐SAT -- Belief Propagation -- satisfiability problem; Random graphs -- Periodicals; Mathematical analysis -- Periodicals; 519
• DOI: 10.1002/rsa.20993
• Languages: English
• ISSNs: 1042-9832

Abstract

Abstract: We show that throughout the satisfiable phase the normalized number of satisfying assignments of a random 2‐SAT formula converges in probability to an expression predicted by the cavity method from statistical physics. The proof is based on showing that the Belief Propagation algorithm renders the correct marginal probability that a variable is set to "true" under a uniformly random satisfying assignment.