The number of satisfying assignments of random 2-SAT formulas

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

Download full text files

Export metadata

Metadaten
Author:Dimitris Achlioptas, Amin Coja-OghlanORCiDGND, Maximilian Grischa Hahn-KlimrothORCiDGND, Joon Lee, Noëla Müller, Manuel PenschuckGND, Guangyan Zhou
URN:urn:nbn:de:hebis:30:3-621658
DOI:https://doi.org/10.1002/rsa.20993
ISSN:1098-2418
Parent Title (English):Random structures & algorithms
Publisher:Wiley
Place of publication:New York, NY [u.a.]
Document Type:Article
Language:English
Date of Publication (online):2021/01/17
Date of first Publication:2021/01/17
Publishing Institution:Universitätsbibliothek Johann Christian Senckenberg
Release Date:2021/11/03
Tag:2-SAT; Belief Propagation; satisfiability problem
Volume:58
Issue:4
Page Number:39
First Page:609
Last Page:647
Note:
DFG Stiftung Polytechnische Gesellschaft DFG ME National Natural Science Foundation of China. Grant Numbers: CO 646/4, 2088/3-2, ME 2088/4-2, 61702019
HeBIS-PPN:489346618
Institutes:Informatik und Mathematik
Dewey Decimal Classification:5 Naturwissenschaften und Mathematik / 51 Mathematik / 510 Mathematik
Sammlungen:Universitätspublikationen
Licence (German):License LogoCreative Commons - Namensnennung 4.0

OPUS4 Logo