The Number of Satisfying Assignments of Random Regular<i>k</i>-SAT Formulas

Abstract

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.