The random 2-SAT partition function

DOI10.1002/RSA.20993MaRDI QIDQ6334473zbMATH OpenFDO

Authors D. Achlioptas, Amin Coja-Oghlan, Max Hahn-Klimroth, Joon Sang Lee, Noela Müller, Manuel Penschuck, Guangyan Zhou

Publication date 10 February 2020

Full work available at URL https://doi.org/10.1002/RSA.20993

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Combinatorial probability (60C05) Probability in computer science (algorithm analysis, random structures, phase transitions, etc.) (68Q87)

Abstract: We show that throughout the satisfiable phase the normalised 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.

This page was built for publication: The random 2-SAT partition function

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6334473)