2010/04/14 by Rathi, Vishwambhar, Aurell, Erik, Rasmussen, Lars +1
#Computational Complexity (cs.CC) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #Information Theory (cs.IT)
paper · doi:10.48550/arxiv.1004.2425
We consider the regular balanced model of formula generation in conjunctive normal form (CNF) introduced by Boufkhad, Dubois, Interian, and Selman. We say that a formula is p-satisfying if there is a truth assignment satisfying 1-2-k+p 2-k fraction of clauses. Using the first moment method we determine upper bound on the threshold clause density such that there are no p-satisfying assignments with high probability above this upper bound. There are two aspects in deriving the lower bound using the second moment method. The first aspect is, given any p ∈ (0,1) and k, evaluate the lower bound on the threshold. This evaluation is numerical in nature. The second aspect is to derive the lower bound as a function of p for large enough k. We address the first aspect and evaluate the lower bound on the p-satisfying threshold using the second moment method. We observe that as k increases the lower bound seems to converge to the asymptotically derived lower bound for uniform model of formula generation by Achlioptas, Naor, and Peres.