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

Onderzoeksoutput: Bijdrage aan tijdschrift › Tijdschriftartikel › Academic › peer review

6 Citaten (Scopus)

Samenvatting

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.

Originele taal-2	Engels
Pagina's (van-tot)	609-647
Aantal pagina's	39
Tijdschrift	Random Structures and Algorithms
Volume	58
Nummer van het tijdschrift	4
DOI's	https://doi.org/10.1002/rsa.20993
Status	Gepubliceerd - jul. 2021
Extern gepubliceerd	Ja

Toegang tot document

10.1002/rsa.20993

Andere bestanden en links

Link naar publicatie in Scopus

Citeer dit

@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 - http://www.scopus.com/inward/record.url?scp=85099385027&partnerID=8YFLogxK

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

Samenvatting

Toegang tot document

Andere bestanden en links

Vingerafdruk

Citeer dit