Solution space heterogeneity of the randomK-satisfiability problem: Theory and simulations
Haijun Zhou · Journal of Physics Conference Series · 2010
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 α reaches a critical value α 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 α reaches a larger threshold value α 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.