Palabras clave
planted model
belief propagation
Cómo citar
Resumen
En este trabajo estudiamos el comportamiento del algoritmo Belief Propagation (BP) en la resolución de dos problemas de optimización combinatoria: 3-SAT y 3-XORSAT. Aplicamos BP a la versión plantada de estos problemas cuando una fracción de las variables está fija desde el inicio. La probabilidad de resolver una instancia usando esta inicialización informada muestra cambios abruptos con el número de variables fijadas. En ambos problemas estudiados BP requiere menos variables fijadas que el algoritmo de Monte Carlo para converger a una solución. Finalmente, extendemos una conocida descripción analítica del algoritmo Unit Clause Propagation para predecir con precisión el comportamiento de BP aplicado al 3-XORSAT en grafos aleatorios regulares con inicialización informada.
Referencias
[1] Robert Dorfman, Paul A. Samuelson, and Robert M. So- low. Linear programming and economic analysis / Robert Dorf- man, Paul A. Samuelson, Robert M. Solow. «The »Rand series. McGraw-Hill Kogakusha, New York [etc.] Tokyo, international student ed edition, c1958.
[2] S. Cook. The complexity of theorem-proving procedures. In Proceedings of the 3rd Annual ACM Symposium on Theory of Computing, page 151. ACM, 1971.
[3] Marc Mezard and Andrea Montanari. Information, physics, and computation. Oxford University Press, 2009.
[4] M. Mezard, G. Parisi, and R. Zecchina. Analytic and al- gorithmic solution of random satisfiability problems. Science, 297(5582):812–815, 2002.
[5] Florant Krzakala, Andrea Montanari, Federico Ricci- Tersenghi, and Lenka Zdeborová. Gibbs states and the set of solutions of random constraint satisfaction problems. Procee- dings of the National Academy of Science, 104:10319–10322, 2007.
[6] Mikko Alava, John Ardelius, Erik Aurell, Petteri Kaski, Su- priya Krishnamurthy, Pekka Orponen, and Sakari Seitz. Cir- cumspect descent prevails in solving random constraint satisfac- tion problems. Proceedings of the National Academy of Scien- ces, 105(40):15253–15257, 2008.
[7] Dimitris Achlioptas and Amin Coja-Oghlan. Algorithmic barriers from phase transitions. In 2008 49th Annual IEEE Symposium on Foundations of Computer Science, pages 793– 802, 2008.
[8] E. Aurell, E. Domínguez, D. Machado, and R. Mulet. A theory of non-equilibrium local search on random satisfaction problems. Physical Review Letters, 123:230602, 2019.
[9] CH Papadimitriou. On selecting a satisfying truth assign- ment. In New York IEEE Computer Society, editor, Proceedings of the 32nd IEEE Symposium on the Foundations of Computer Science, volume FOCS-91, page 163–169, 1991.
[10] Erik Aurell, Uri Gordon, and Scott Kirkpatrick. Comparing beliefs, surveys, and random walks. In L. Saul, Y. Weiss, and
L. Bottou, editors, Advances in Neural Information Processing Systems, volume 17. MIT Press, 2004. 9, 1991.
[11] Sakari Seitz, Mikko Alava, and Pekka Orponen. Focused local search for random 3-satisfiability. Journal of Statistical Me- chanics: Theory and Experiment, 2005(06):P06006, jun 2005.
[12] S. Kirkpatrick, C. D. Gelatt, and M. P. Vecchi. Optimization by simulated annealing. Science, 220(4598):671–680, 1983.
[13] Maria Chiara Angelini and Federicco Ricci-Tersenghi. Limits and performances of algorithms based on simulated annealing in solving sparse hard inference problems. Physical Review X, 13:021011, 2023.
[14] Federico Ricci-Tersenghi and Guilhem Semerjian. On the cavity method for decimated random constraint satisfaction problems and the analysis of belief propagation guided deci- mation algorithms. Journal of Statistical Mechanics: Theory and Experiment, 2009(09):P09001, sep 2009.
[15] Louise Budzynski, Federico Ricci-Tersenghi, and Guilhem Semerjian. Biased landscapes for random constraint satisfac- tion problems. Journal of Statistical Mechanics: Theory and Experiment, 2019(2):023302, feb 2019.
[16] Federico Ricci-Tersenghi, Martin Weigt, and Riccardo Zec- china. Simplest random k-satisfiability problem. Physical Re- view E, 63:026702, Jan 2001.
[17] Silvio Franz, Michele Leone, Federico Ricci-Tersenghi, and Riccardo Zecchina. Exact solutions for diluted spin glasses and optimization problems. Physical Review Letters, 87:127209, Aug 2001.
[18] Andrea Montanari and Federico Ricci-Tersenghi. Cooling schedule dependence of the dynamics of mean-field glasses. Phys. Rev. B, 70:134406, Oct 2004.
[19] Matteo Bellitti, Federico Ricci-Tersenghi, and Antonello Scardicchio. Entropic barriers as a reason for hardness in both classical and quantum algorithms. Phys. Rev. Res., 3:043015, Oct 2021.
[20] M. Bernaschi, M. Bisson, M. Fatica, E. Marinari, V. Martin- Mayor, G. Parisi, and F. Ricci-Tersenghi. How we are leading a 3-xorsat challenge: From the energy landscape to the algo- rithm and its efficient implementation on gpus(a). Europhysics Letters, 133(6):60005, may 2021.
[21] Stephan Mertens, Marc Mézard, and Riccardo Zecchina. Th- reshold values of random k-sat from the cavity method. Random Structures & Algorithms, 28(3):340–373, 2006.
[22] Andrea Montanari, Federico Ricci-Tersenghi, and Guilhem Semerjian. Clusters of solutions and replica symmetry brea- king in random k-satisfiability. Journal of Statistical Mecha- nics: Theory and Experiment, 2008(04):P04004, apr 2008.
[23] Haijun Zhou. Glassy behavior and jamming of a random walk process for sequentially satisfying a constraint satisfaction formula. Eur. Phys. J. B, 73(4):617–624, 2010.
[24] Florent Krzakala and Jorge Kurchan. Landscape analysis of constraint satisfaction problems. Phys. Rev. E, 76:021122, Aug 2007.
[25] Maria Chiara Angelini and Federico Ricci-Tersenghi. Monte carlo algorithms are very effective in finding the largest inde- pendent set in sparse random graphs. Phys. Rev. E, 100:013302, Jul 2019.
[26] Angelo Giorgio Cavaliere and Federico Ricci-Tersenghi. Bia- sed thermodynamics can explain the behaviour of smart op- timization algorithms that work above the dynamical th- reshold. Journal of Statistical Mechanics: Theory and Expe- riment, 2025(5):053405, may 2025.
[27] David Gamarnik and Madhu Sudan. Limits of local algo- rithms over sparse random graphs. In Proceedings of the 5th Conference on Innovations in Theoretical Computer Science, ITCS ’14, page 369–376, New York, NY, USA, 2014. Associa- tion for Computing Machinery.
[28] David Gamarnik and Aukosh Jagannath. The overlap gap property and approximate message passing algorithms for $p$- spin models. The Annals of Probability, 2019.
[29] W. Barthel, A. K. Hartmann, M. Leone, F. Ricci-Tersenghi,
M. Weigt, and R. Zecchina. Hiding solutions in random sa- tisfiability problems: A statistical mechanics approach. Phys. Rev. Lett., 88:188701, Apr 2002.
[30] Florent Krzakala and Lenka Zdeborová. Hiding quiet solutions in random constraint satisfaction problems. Phys. Rev. Lett., 102:238701, Jun 2009.
[31] Francesco Zamponi. Mean field theory of spin glasses. arXiv, 1008.4844, 2014.
[32] Nicholas Metropolis, AriannaW. Rosenbluth, Marshall N. Rosenbluth, Augusta H. Teller, and Edward Teller. Equation of state calculations by fast computing machines. The Journal of Chemical Physics, 21(6):1087–1092, 06 1953.
[33] E. Aurell, E. Domínguez, D. Machado, and R. Mulet. Exploring the diluted ferromagnetic p-spin model with a cavity master equation. Physical Review E, 97:05103(R), 2018.
[34] E. Aurell, G. Del Ferraro, E. Domínguez, and R. Mulet. A cavity master equation for the continuous time dynamics of discrete spins models. Physical Review E, 95:052119, 2017.
[35] E. Domínguez, D. Machado, and R. Mulet. The cavity master equation: average and fixed point of the ferromagnetic model in random graphs. Journal of Statistical Mechanics: Theory and Experiment, 2020:073304, 2020.
Esta obra está bajo una licencia internacional Creative Commons Atribución-NoComercial 4.0.
Derechos de autor 2026 Sociedad Cubana de Física & Facultad de Física de la Universidad de La Habana