Satisfiability threshold for random regular NAE-SAT

ABSTRACT

We consider the random regular k-nae-sat problem with n variables each appearing in exactly d clauses. For all k exceeding an absolute constant k₀, we establish explicitly the satisfiability threshold d_* ∈ d_*(k). We prove that for d < d_* the problem is satisfiable with high probability while for d > d_* the problem is unsatisfiable with high probability. If the threshold d_* lands exactly on an integer, we show that the problem is satisfiable with probability bounded away from both zero and one. This is the first result to locate the exact satisfiability threshold in a random constraint satisfaction problem exhibiting the condensation phenomenon identified by Krzakał a et al. (2007). Our proof verifies the onestep replica symmetry breaking formalism for this model. We expect our methods to be applicable to a broad range of random constraint satisfaction problems and combinatorial problems on random graphs.

References

1. D. Achlioptas and C. Moore. Random k-sat: two moments suffice to cross a sharp threshold. SIAM J. Comput., 36(3):740--762 (electronic), 2006.
2. D. Achlioptas, A. Naor, and Y. Peres. Rigorous location of phase transitions in hard optimization problems. Nature, 435(7043):759--764, 2005.
3. D. Achlioptas and Y. Peres. The threshold for random k-sat is 2^k log 2 --- O(k). J. Amer. Math. Soc., 17(4):947--973 (electronic), 2004.
4. D. Achlioptas and F. Ricci-Tersenghi. Random formulas have frozen variables. SIAM J. Comput., 39(1):260--280, 2009.
5. E. Aurell, U. Gordon, and S. Kirkpatrick. Comparing beliefs, surveys, and random walks. In NIPS, 2004.
6. A. Braunstein, M. Mézard, and R. Zecchina. Survey propagation: an algorithm for satisfiability. Random Struct. Algor., 27(2):201--226, 2005.
7. A. Braunstein and R. Zecchina. Survey propagation as local equilibrium equations. J. Stat. Mech. Theory E., 2004(06):P06007, 2004.
8. T. Castellani, V. Napolano, F. Ricci-Tersenghi, and R. Zecchina. Bicolouring random hypergraphs. J. Phys. A, 36(43):11037--11053, 2003.
9. V. Chvátal and B. Reed. Mick gets some (the odds are on his side). In Proc. IEEE Symp. (FOCS), pages 620--627, 1992.
10. A. Coja-Oghlan. Random regular k-sat. Preprint at http://arxiv.org/abs/1310.2728v1, 2013.
11. A. Coja-Oghlan. The asymptotic k-sat threshold. In Proc. ACM Symp. (STOC), 2014.
12. A. Coja-Oghlan and K. Panagiotou. Catching the k-naesat threshold. In Proc. ACM Symp. (STOC), pages 899--907. ACM, New York, 2012.
13. A. Coja-Oghlan and K. Panagiotou. Going after the k-sat threshold. In Proc. ACM Symp. (STOC), pages 705--714, New York, NY, USA, 2013. ACM.
14. A. Coja-Oghlan and D. Vilenchik. Chasing the k-colorability threshold. In Proc. IEEE Symp. (FOCS), pages 380--389, Oct 2013.
15. A. Coja-Oghlan and L. Zdeborová. The condensation transition in random hypergraph 2-coloring. In Proc. ACM-SIAM Symp. (SODA), pages 241--250. SIAM, 2012.
16. L. Dall'Asta, A. Ramezanpour, and R. Zecchina. Entropy landscape and non-Gibbs solutions in constraint satisfaction problems. Phys. Rev. E (3), 77(3):031118, 16, 2008.
17. A. Dembo, A. Montanari, A. Sly, and N. Sun. The replica symmetric solution for Potts models on d-regular graphs. Comm. Math. Phys., 2014.
18. A. Dembo, A. Montanari, and N. Sun. Factor models on locally tree-like graphs. Ann. Probab., 41(6):4162--4213, 2013.
19. J. Ding, A. Sly, and N. Sun. Maximum independent sets on random regular graphs. Preprint at http://arxiv.org/abs/1310.4787, 2013.
20. W. Fernandez de la Vega. Random 2-sat: results and problems. Theoretical Computer Science, 265(1):131--146, 2001.
21. E. Friedgut. Sharp thresholds of graph properties, and the k-sat problem. J. Amer. Math. Soc., 12(4):1017--1054, 1999. With an appendix by Jean Bourgain.
22. A. Galanis, D. Štefankovič, and E. Vigoda. Inapproximability for antiferromagnetic spin systems in the tree non-uniqueness region. In Proc. ACM Symp. (STOC), 2014.
23. A. Goerdt. A threshold for unsatisfiability. J. Comput. System Sci., 53(3):469--486, 1996.
24. S. Janson, T. Łuczak, and A. Rucinski. Random graphs. Wiley-Interscience Series in Discrete Mathematics and Optimization. Wiley-Interscience, New York, 2000.
25. F. Krzakała, A. Montanari, F. Ricci-Tersenghi, G. Semerjian, and L. Zdeborová. Gibbs states and the set of solutions of random constraint satisfaction problems. P. Natl. Acad. Sci., 104(25):10318--10323, 2007.
26. E. Maneva, E. Mossel, and M. J. Wainwright. A new look at survey propagation and its generalizations. J. ACM, 54(4):Art. 17, 41, 2007.
27. E. Maneva and A. Sinclair. On the satisfiability threshold and clustering of solutions of random 3-sat formulas. Theoret. Comput. Sci., 407(1-3):359--369, 2008.
28. M. Mézard and A. Montanari. Information, physics, and computation. Oxford Graduate Texts. Oxford University Press, Oxford, 2009.
29. M. Mézard, T. Mora, and R. Zecchina. Clustering of solutions in the random satisfiability problem. Phys. Rev. Lett., 94(19):197205, 2005.
30. M. Mézard and G. Parisi. Replicas and optimization. Journal de Physique Lettres, 46(17):771--778, 1985.
31. M. Mézard and G. Parisi. The Bethe lattice spin glass revisited. Eur. Phys. J. B, 20(2):217--233, 2001.
32. M. Mézard and G. Parisi. The cavity method at zero temperature. J. Stat. Phys., 111(1-2):1--34, 2003.
33. M. Mézard, G. Parisi, and R. Zecchina. Analytic and algorithmic solution of random satisfiability problems. Science, 297(5582):812--815, 2002.
34. M. Mézard, F. Ricci-Tersenghi, and R. Zecchina. Two solutions to diluted p-spin models and xorsat problems. J. Stat. Phys., 111(3-4):505--533, 2003.
35. M. Molloy and R. Restrepo. Frozen variables in random boolean constraint satisfaction problems. In Proc. ACM Symp. (SODA), pages 1306--1318. SIAM, 2013.
36. R. Monasson, R. Zecchina, S. Kirkpatrick, B. Selman, and L. Troyansky. Determining computational complexity from characteristic "phase transitions". Nature, 400(6740):133--137, 1999.
37. A. Montanari, F. Ricci-Tersenghi, and G. Semerjian. Clusters of solutions and replica symmetry breaking in random k-satisfiability. J. Stat. Mech. Theory E., 2008(04):P04004, 2008.
38. B. Pittel and G. B. Sorkin. The satisfiability threshold for k-xorsat. Preprint at http://arxiv.org/abs/1212.1905, 2012.
39. R. W. Robinson and N. C. Wormald. Almost all cubic graphs are Hamiltonian. Random Struct. Algor., 3(2):117--125, 1992.
40. R. W. Robinson and N. C. Wormald. Almost all regular graphs are Hamiltonian. Random Struct. Algor., 5(2):363--374, 1994.
41. N. C. Wormald. Models of random regular graphs. In Surveys in combinatorics, 1999 (Canterbury), volume 267 of London Math. Soc. Lecture Note Ser., pages 239--298. Cambridge Univ. Press, Cambridge, 1999.

Index Terms

• Mathematics of computing

  • Discrete mathematics

    • Graph theory