Hostname: page-component-745bb68f8f-kw2vx Total loading time: 0 Render date: 2025-02-06T16:48:04.759Z Has data issue: false hasContentIssue false
  • English
  • Français

The Number of Satisfying Assignments of Random Regular k-SAT Formulas

Published online by Cambridge University Press:  20 June 2018

AMIN COJA-OGHLAN  and
NICK WORMALD
AMIN COJA-OGHLAN
Affiliation:
Mathematics Institute, Goethe University, 10 Robert-Mayer-Straß e, Frankfurt 60325, Germany (e-mail: acoghlan@math.uni-frankfurt.de)
NICK WORMALD
Affiliation:
Department of Mathematical Sciences, Monash University, VIC 3800, Australia (e-mail: nick.wormald@monash.edu)
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the ‘Save PDF’ action button.

Let Φ be a random k-SAT formula in which every variable occurs precisely d times positively and d times negatively. Assuming that k is sufficiently large and that d is slightly below the critical degree where the formula becomes unsatisfiable with high probability, we determine the limiting distribution of the number of satisfying assignments.

Keywords

Primary 60C05Secondary 05C80
Type
Paper
Information
Combinatorics, Probability and Computing , Volume 27 , Special Issue 4: Special Issue: Oberwolfach Workshop , July 2018 , pp. 496 - 530
Copyright
Copyright © Cambridge University Press 2018 

References

[1] Achlioptas, D. and Coja-Oghlan, A. (2008) Algorithmic barriers from phase transitions. In FOCS 2008: 49th Annual IEEE Symposium on Foundations of Computer Science, IEEE, pp. 793–802.CrossRefGoogle Scholar
[2] Achlioptas, D. and Moore, C. (2006) Random k-SAT: Two moments suffice to cross a sharp threshold. SIAM J. Comput. 36 740–762.Google Scholar
[3] Achlioptas, D., Naor, A. and Peres, Y. (2005) Rigorous location of phase transitions in hard optimization problems. Nature 435 759–764.CrossRefGoogle ScholarPubMed
[4] Achlioptas, D. and Peres, Y. (2004) The threshold for random k-SAT is 2k ln 2 - O(k). J. Amer. Math. Soc. 17 947–973.Google Scholar
[5] Bapst, V. and Coja-Oghlan, A. (2016) The condensation phase transition in the regular k-SAT model. In RANDOM 2016: 20th International Workshop on Approximation, Randomization, and Combinatorial Optimization, Springer, #22.Google Scholar
[6] Bollobas, B. (2001) Random Graphs, second edition, Cambridge University Press.Google Scholar
[7] Békéssy, A., Békéssy, P. and Komlós, J. (1972) Asymptotic enumeration of regular matrices. Studia Sci. Math. Hungar. 7 343–353.Google Scholar
[8] Bolthausen, E. (1984) An estimate of the remainder in a combinatorial central limit theorem. Z. Wahr. Verw. Gebiete 66 379–386.Google Scholar
[9] Coja-Oghlan, A. and Panagiotou, K. (2016) The asymptotic k-SAT threshold. Adv. Math. 288 985–1068.Google Scholar
[10] Coja-Oghlan, A. and Panagiotou, K. (2013) Going after the k-SAT threshold. In STOC 2013: 45th Annual ACM Symposium on Theory of Computing, ACM, pp. 705–714.Google Scholar
[11] Coja-Oghlan, A. and Vilenchik, D. (2013) Chasing the k-colorability threshold. In FOCS 2013: IEEE 54th Annual Symposium on Foundations of Computer Science, IEEE, pp. 380–389.Google Scholar
[12] Coja-Oghlan, A. and Zdeborová, L. (2012) The condensation transition in random hypergraph 2-coloring. In SODA 2012: 23rd Annual ACM–SIAM Symposium on Discrete Algorithms, SIAM, pp. 241–250.CrossRefGoogle Scholar
[13] Davis, B. and McDonald, D. (1995) An elementary proof of the local central limit theorem. J. Theoret. Probab. 8 693–701.Google Scholar
[14] Ding, J., Sly, A. and Sun, N. (2014) Satisfiability threshold for random regular NAE-SAT. In STOC 2014: 46th Annual ACM Symposium on Theory of Computing, ACM, pp. 814–822.Google Scholar
[15] Ding, J., Sly, A. and Sun, N. (2015) Proof of the satisfiability conjecture for large k. In STOC 2015: Proc. 47th Annual ACM Symposium on Theory of Computing, ACM, pp. 59–68.Google Scholar
[16] Frieze, A. and Wormald, N. C. (2005) Random k-Sat: A tight threshold for moderately growing k. Combinatorica 25 297–305.Google Scholar
[17] Janson, S. (1995) Random regular graphs: Asymptotic distributions and contiguity. Combin. Probab. Comput. 4 369–405.Google Scholar
[18] Kirousis, L., Kranakis, E., Krizanc, D. and Stamatiou, Y. (1998) Approximating the unsatisfiability threshold of random formulas. Random Struct. Alg. 12 253–269.3.0.CO;2-U>CrossRefGoogle Scholar
[19] Mézard, M., Parisi, G. and Zecchina, R. (2002) Analytic and algorithmic solution of random satisfiability problems. Science 297 812–815.Google Scholar
[20] Molloy, M., Robalewska, H., Robinson, R. W. and Wormald, N. C. (1997) 1-factorisations of random regular graphs. Random Struct. Alg. 10 305–321.Google Scholar
[21] Rassmann, F. (2016) On the number of solutions in random hypergraph 2-colouring. Electron. J. Combin. 24 3.11.Google Scholar
[22] Rathi, V., Aurell, E., Rasmussen, L. K. and Skoglund, M. (2010) Bounds on threshold of regular random k-SAT. In SAT 2010: 12th International Conference on Theory and Applications of Satisfiability Testing, Springer, pp. 264–277.Google Scholar
[23] Robinson, R. W. and Wormald, N. C. (1992) Almost all cubic graphs are Hamiltonian. Random Struct. Alg. 3 117–125.CrossRefGoogle Scholar
[24] Sly, A., Sun, N. and Zhang, Y. (2016) The number of solutions for random regular NAE-SAT. Proc. 57th FOCS 724–731.Google Scholar
[25] Wormald, N. C. (1978) Some problems in the enumeration of labelled graphs. Doctoral thesis, Newcastle University.Google Scholar