Communities of solutions in single solution clusters of a random K-Satisfiability formula

Details Communities of solutions in single solution clusters of a random K-Satisfiability formula Communities of solutions in single solution clusters of a random K-Satisfiability formula

2009-03-17

arxiv.org/abs/0903.2908v3

Phys. Rev. E 80, 066108 (2009)

Physics

Condensed Matter

Disordered Systems and Neural Networks

Extensively revised and expanded into 15 pages with 10 figures. New mean-field calculations and simulation results added

Scientific paper

10.1103/PhysRevE.80.066108

The solution space of a K-satisfiability (K-SAT) formula is a collection of solution clusters, each of which contains all the solutions that are mutually reachable through a sequence of single-spin flips. Knowledge of the statistical property of solution clusters is valuable for a complete understanding of the solution space structure and the computational complexity of the random K-SAT problem. This paper explores single solution clusters of random 3- and 4-SAT formulas through unbiased and biased random walk processes and the replica-symmetric cavity method of statistical physics. We find that the giant connected component of the solution space has already formed many different communities when the constraint density of the formula is still lower than the solution space clustering transition point. Solutions of the same community are more similar with each other and more densely connected with each other than with the other solutions. The entropy density of a solution community is calculated using belief propagation and is found to be different for different communities of the same cluster. When the constraint density is beyond the clustering transition point, the same behavior is observed for the solution clusters reached by several stochastic search algorithms. Taking together, the results of this work suggests a refined picture on the evolution of the solution space structure of the random K-SAT problem; they may also be helpful for designing new heuristic algorithms.

Affiliated with

Also associated with

No associations

Rating

Communities of solutions in single solution clusters of a random K-Satisfiability formula 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 Communities of solutions in single solution clusters of a random K-Satisfiability formula, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Communities of solutions in single solution clusters of a random K-Satisfiability formula will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-491109