The number of satisfying assignments of random 2-SAT formulas

Dimitris Achlioptas; Amin Coja-Oghlan; Max Hahn-Klimroth; Joon Lee; Noela Müller; Manuel Penschuk; Guangyan Zhou

doi:10.1002/rsa.20993

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 journal › Article › Academic › peer-review

10 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 language	English
Pages (from-to)	609-647
Number of pages	39
Journal	Random Structures and Algorithms
Volume	58
Issue number	4
DOIs	https://doi.org/10.1002/rsa.20993
Publication status	Published - Jul 2021
Externally published	Yes

Keywords

2-SAT
Belief Propagation
satisfiability problem

Access to Document

10.1002/rsa.20993

Cite this

@article{1d512f91359247b5af02e592090896fb,

title = "The number of satisfying assignments of random 2-SAT formulas",

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.",

keywords = "2-SAT, Belief Propagation, satisfiability problem",

author = "Dimitris Achlioptas and Amin Coja-Oghlan and Max Hahn-Klimroth and Joon Lee and Noela M{\"u}ller and Manuel Penschuk and Guangyan Zhou",

year = "2021",

month = jul,

doi = "10.1002/rsa.20993",

language = "English",

volume = "58",

pages = "609--647",

journal = "Random Structures and Algorithms",

issn = "1042-9832",

publisher = "Wiley",

number = "4",

}

TY - JOUR

T1 - The number of satisfying assignments of random 2-SAT formulas

AU - Achlioptas, Dimitris

AU - Coja-Oghlan, Amin

AU - Hahn-Klimroth, Max

AU - Lee, Joon

AU - Müller, Noela

AU - Penschuk, Manuel

AU - Zhou, Guangyan

PY - 2021/7

Y1 - 2021/7

N2 - 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.

AB - 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.

KW - 2-SAT

KW - Belief Propagation

KW - satisfiability problem

UR - https://www.scopus.com/pages/publications/85099385027

U2 - 10.1002/rsa.20993

DO - 10.1002/rsa.20993

M3 - Article

SN - 1042-9832

VL - 58

SP - 609

EP - 647

JO - Random Structures and Algorithms

JF - Random Structures and Algorithms

IS - 4

ER -

The number of satisfying assignments of random 2-SAT formulas

Abstract

Keywords

Access to Document

Other files and links

Fingerprint

Cite this