Bounds on Threshold of Regular Random $k$-SAT

Details Bounds on Threshold of Regular Random $k$-SAT Bounds on Threshold of Regular Random $k$-SAT

2010-02-05

arxiv.org/abs/1002.1290v3

Computer Science

Information Theory

Accepted to SAT 2010

Scientific paper

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 \geq 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 \cite{AcM06} regarding the performance of the second moment method for regular random formulas.

Affiliated with

Also associated with

No associations

Rating

Bounds on Threshold of Regular Random $k$-SAT 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 Threshold of Regular Random $k$-SAT, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Bounds on Threshold of Regular Random $k$-SAT will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-536233