Solution space heterogeneity of the random K-satisfiability problem: Theory and simulations
The random A-satisfiability (K -SAT) problem is an important problem for studying typical-case complexity of NP-eomplete combinatorial satisfaction; it is also a representative model of finiteconnectivity spin-glosses. In this paper we review our recent efforts on the solution space fine structures of the random A-SAT problem. A heterogeneity transition is predicted to occur in the solution space as the constraint density r> 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 SEQ3AT. which performs a random walk of single-spin flips, is investigated. The relevance of this work to glassy dynamics studies is briefly mentioned.
Haijun Zhou
Key Laboratory of Frontiers in Theoretical Physics, Institute of Theoretical Physics, Chinese Academy of Sciences, Beijing 100190. China KavIi Institute for Theoretical Physics China (KITPC) at the Chinese Academy of Sciences, Beijing 100190, China
国际会议
International Workshop on Statistical Physics and Computer Sciences(统计物理与计算机科学交叉研究国际研讨会 )
北京
英文
310-320
2010-07-08（万方平台首次上网日期，不代表论文的发表时间）