Computer Science – Information Theory
Scientific paper
2010-04-14
Computer Science
Information Theory
6th International symposium on turbo codes & iterative information processing, 2010
Scientific paper
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 \in (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.
Aurell Erik
Rasmussen Lars
Rathi Vishwambhar
Skoglund Mikael
No associations
LandOfFree
Bounds on Thresholds Related to Maximum Satisfiability of Regular Random Formulas does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Bounds on Thresholds Related to Maximum Satisfiability of Regular Random Formulas, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Bounds on Thresholds Related to Maximum Satisfiability of Regular Random Formulas will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-528057