Solution space heterogeneity of the random K-satisfiability problem: Theory and simulations

Details Solution space heterogeneity of the random K-satisfiability problem: Theory and simulations Solution space heterogeneity of the random K-satisfiability problem: Theory and simulations

2010-01-18

arxiv.org/abs/1001.2951v2

Physics

Condensed Matter

Disordered Systems and Neural Networks

11 pages, 4 figures. Final version as will appear in Journal of Physics: Conference Series (Proceedings of the International W

Scientific paper

The random K-satisfiability (K-SAT) problem is an important problem for studying typical-case complexity of NP-complete combinatorial satisfaction; it is also a representative model of finite-connectivity spin-glasses. In this paper we review our recent efforts on the solution space fine structures of the random K-SAT problem. A heterogeneity transition is predicted to occur in the solution space as the constraint density alpha reaches a critical value alpha_cm. This transition marks the emergency of exponentially many solution communities in the solution space. After the heterogeneity transition the solution space is still ergodic until alpha reaches a larger threshold value alpha_d, at which the solution communities disconnect from each other to become different solution clusters (ergodicity-breaking). The existence of solution communities in the solution space is confirmed by numerical simulations of solution space random walking, and the effect of solution space heterogeneity on a stochastic local search algorithm SEQSAT, which performs a random walk of single-spin flips, is investigated. The relevance of this work to glassy dynamics studies is briefly mentioned.

Affiliated with

Also associated with

No associations

Rating

Solution space heterogeneity of the random K-satisfiability problem: Theory and simulations 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 Solution space heterogeneity of the random K-satisfiability problem: Theory and simulations, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Solution space heterogeneity of the random K-satisfiability problem: Theory and simulations will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-660119