Clusters of solutions and replica symmetry breaking in random k-satisfiability

Physics – Condensed Matter – Disordered Systems and Neural Networks

Scientific paper

Rate now

  [ 0.00 ] – not rated yet Voters 0   Comments 0

Details

30 pages, 14 figures, typos corrected, discussion of appendix C expanded with a new figure

Scientific paper

10.1088/1742-5468/2008/04/P04004

We study the set of solutions of random k-satisfiability formulae through the cavity method. It is known that, for an interval of the clause-to-variables ratio, this decomposes into an exponential number of pure states (clusters). We refine substantially this picture by: (i) determining the precise location of the clustering transition; (ii) uncovering a second `condensation' phase transition in the structure of the solution set for k larger or equal than 4. These results both follow from computing the large deviation rate of the internal entropy of pure states. From a technical point of view our main contributions are a simplified version of the cavity formalism for special values of the Parisi replica symmetry breaking parameter m (in particular for m=1 via a correspondence with the tree reconstruction problem) and new large-k expansions.

No associations

LandOfFree

Say what you really think

Search LandOfFree.com for scientists and scientific papers. Rate them and share your experience with other people.

Rating

Clusters of solutions and replica symmetry breaking in random k-satisfiability 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 Clusters of solutions and replica symmetry breaking in random k-satisfiability, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Clusters of solutions and replica symmetry breaking in random k-satisfiability will most certainly appreciate the feedback.

Rate now

     

Profile ID: LFWR-SCP-O-603731

  Search
All data on this website is collected from public sources. Our data reflects the most accurate information available at the time of publication.