Bounds on Threshold of Regular Random k-SAT

2010/02/05 by Rathi, Vishwambhar, Aurell, Erik, Rasmussen, Lars +1
#Combinatorics (math.CO) #Computational Complexity (cs.CC) #FOS: Computer and information sciences #FOS: Mathematics #Information Theory (cs.IT)

paper · doi:10.48550/arxiv.1002.1290

Abstract

We consider the regular model of formula generation in conjunctive normal form (CNF) introduced by Boufkhad et. al. We derive an upper bound on the satisfiability threshold and NAE-satisfiability threshold for regular random k-SAT for any k ≥ 3. We show that these bounds matches with the corresponding bound for the uniform model of formula generation. We derive lower bound on the threshold by applying the second moment method to the number of satisfying assignments. For large k, we note that the obtained lower bounds on the threshold of a regular random formula converges to the lower bound obtained for the uniform model. Thus, we answer the question posed in \citeAcM06 regarding the performance of the second moment method for regular random formulas.

Related

• Bounds on Thresholds Related to Maximum Satisfiability of Regular Random Formulas
• The Threshold for Random k-SAT is 2^k ln2 - O(k)
• The Asymptotic Order of the k-SAT Threshold
• Structure of random r-SAT below the pure literal threshold
• On the Regularity of Random 2-SAT and 3-SAT