The number of satisfying assignments of random 2-SAT formulas

Dimitris Achlioptas, Amin Coja-Oghlan (Corresponding author), Max Hahn-Klimroth, Joon Lee, Noela Müller, Manuel Penschuk, Guangyan Zhou

Research output: Contribution to journalArticleAcademicpeer-review

8 Citations (Scopus)

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.
Original languageEnglish
Pages (from-to)609-647
Number of pages39
JournalRandom Structures and Algorithms
Volume58
Issue number4
DOIs
Publication statusPublished - Jul 2021
Externally publishedYes

Keywords

  • 2-SAT
  • Belief Propagation
  • satisfiability problem

Fingerprint

Dive into the research topics of 'The number of satisfying assignments of random 2-SAT formulas'. Together they form a unique fingerprint.

Cite this