Bounds on thresholds related to maximum satisfiability of regular random formulas
2010 (English)In: 6th International Symposium on Turbo Codes and Iterative Information Processing (ISTC), 2010, 107-111 p.Conference paper (Refereed)
We consider the regular balanced model of satisfiability formula generation in conjunctive normal form (CNF), where each literal participates in equal number of clauses and there are k literals participating in a clause. We say that a formula is p-satisfying if there is a truth assignment satisfying 1 - 2-k + p2- 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. Based on the numerical evaluation, we observe that as k increases the ratio of the lower bound and the upper bound seems to converge to one.
Place, publisher, year, edition, pages
2010. 107-111 p.
IdentifiersURN: urn:nbn:se:kth:diva-63135DOI: 10.1109/ISTC.2010.5613816ScopusID: 2-s2.0-78649263014OAI: oai:DiVA.org:kth-63135DiVA: diva2:481680
6th International Symposium on Turbo Codes and Iterative Information Processing (ISTC). Brest. 6 September 2010 - 10 September 2010
QC 201201262012-01-222012-01-222012-01-26Bibliographically approved