,
Reweighted belief propagation and quiet planting for random K-SAT
Journal on Satisfiability, Boolean Modeling and Computation, (25.03.2014)
Аннотация
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.
