The number of satisfying assignments of random regular k-SAT formulas

2016/11/10 by Amin Coja‐Oghlan, Coja-Oghlan, Amin, Nick Wormald +1 · 1 citation
Computer Science · #60C05 #Combinatorics (math.CO) #Constraint Satisfaction and Optimization #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #Rough Sets and Fuzzy Logic

paper · pdf · doi:10.48550/arxiv.1611.03236

openalex publication_date 2016/11/10 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

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 logarithm of the number of satisfying assignments.

Cited by

• The random k-SAT Gibbs uniqueness threshold revisited

Related

• The number of random 2-SAT solutions is asymptotically log-normal
• The Threshold for Random k-SAT is 2^k ln2 - O(k)
• Counting good truth assignments of random k-SAT formulae
• On the satisfiability of random regular signed SAT formulas
• Bounds on Threshold of Regular Random k-SAT