On the Satisfiability Threshold and Clustering of Solutions of Random 3-SAT Formulas

Details On the Satisfiability Threshold and Clustering of Solutions of Random 3-SAT Formulas On the Satisfiability Threshold and Clustering of Solutions of Random 3-SAT Formulas

2007-10-03

arxiv.org/abs/0710.0805v3

Computer Science

Computational Complexity

Scientific paper

We study the structure of satisfying assignments of a random 3-SAT formula. In particular, we show that a random formula of density 4.453 or higher almost surely has no non-trivial "core" assignments. Core assignments are certain partial assignments that can be extended to satisfying assignments, and have been studied recently in connection with the Survey Propagation heuristic for random SAT. Their existence implies the presence of clusters of solutions, and they have been shown to exist with high probability below the satisfiability threshold for k-SAT with k>8, by Achlioptas and Ricci-Tersenghi, STOC 2006. Our result implies that either this does not hold for 3-SAT or the threshold density for satisfiability in 3-SAT lies below 4.453. The main technical tool that we use is a novel simple application of the first moment method.

Affiliated with

Also associated with

No associations

Rating

On the Satisfiability Threshold and Clustering of Solutions of Random 3-SAT 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 On the Satisfiability Threshold and Clustering of Solutions of Random 3-SAT Formulas, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and On the Satisfiability Threshold and Clustering of Solutions of Random 3-SAT Formulas will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-285913