Reweighted belief propagation and quiet planting for random K-SAT

Details Reweighted belief propagation and quiet planting for random K-SAT Reweighted belief propagation and quiet planting for random K-SAT

2012-03-25

arxiv.org/abs/1203.5521v2

Physics

Condensed Matter

Disordered Systems and Neural Networks

13, pages, 4 figures

Scientific paper

We study the random K-satisfiability problem using a partition function where each solution is reweighed according to the number of variables that satisfy every clause. We apply belief propagation and the related cavity method to the reweighed partition function. This allows us to obtain several new results on the properties of random K-satisfiability problem. In particular the reweighing allows to introduce a planted ensemble that generates instances that are, in some region of parameters, equivalent to random instances. We are hence able to generate at the same time a typical SAT instance and one of its solutions. We study the relation between clustering and belief propagation fixed points and we give a direct evidence for the existence of purely entropic (rather than energetic) barriers between clusters in some region of parameters in the random K-satisfiability problem. We show explicitly how to find solutions of random K-SAT leading to a non-trivial whitening core; such solutions were known to exist but were so far never found on large instances. Finally, we discuss algorithmic hardness of such planted instances and determine a region of parameters in which planting leads to satisfiable benchmarks that, up to our knowledge, are the hardest known.

Affiliated with

Also associated with

No associations

Rating

Reweighted belief propagation and quiet planting for 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 Reweighted belief propagation and quiet planting for random K-SAT, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Reweighted belief propagation and quiet planting for random K-SAT will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-75188