Computer Science – Discrete Mathematics
Scientific paper
2011-07-14
Computer Science
Discrete Mathematics
Scientific paper
The estimation of phase transitions in random boolean Constraint Satisfaction Problems (CSP) is based on two fundamental tools: the first and second moment methods. While the first moment method on the number of solutions permits to compute upper bounds on any boolean CSP, the second moment method used for computing lower bounds proves to be more tricky and in most cases gives only the trivial lower bound 0. In this paper, we define a subclass of boolean CSP covering the monotone versions of many known NP-Complete boolean CSPs. We give a method for computing non trivial lower bounds for any member of this subclass. This is achieved thanks to an application of the second moment method to some selected solutions called characteristic solutions that depend on the boolean CSP considered. We apply this method with a finer analysis to establish that the threshold $r_{k}$ (ratio : #constrains/#variables) of monotone 1-in-k-SAT is $\log k/k\leq r_{k}\leq\log^{2}k/k$.
Boufkhad Yacine
Dubois Olivier
No associations
LandOfFree
Second moment method for a family of boolean CSP 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 Second moment method for a family of boolean CSP, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Second moment method for a family of boolean CSP will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-224819