Solution space heterogeneity of the random K-satisfiability problem: Theory and simulations
文献类型：会议论文
| 作者 | Zhou, HJ
|
| 出版日期 | 2010 |
| 会议日期 | MAR 07-10, 2010 |
| 会议地点 | Kyoto Univ, Kyoto, JAPAN |
| 关键词 | CONSTRAINT SATISFACTION PROBLEMS SPIN-GLASSES MEAN-FIELD DYNAMICS LIQUIDS STATES |
| 卷号 | 233 |
| DOI | 10.1088/1742-6596/233/1/012011 |
| 页码 | 12011 |
| 英文摘要 | 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. |
| 源文献作者 | Kyoto Univ |
| 会议录 | INTERNATIONAL WORKSHOP ON STATISTICAL-MECHANICAL INFORMATICS 2010 (IW-SMI 2010)
 |
| 会议录出版者 | IOP PUBLISHING LTD |
| 会议录出版地 | BRISTOL |
| 语种 | 英语 |
| URL标识 | 查看原文 |
| ISSN号 | 1742-6588 |
| WOS研究方向 | Computer Science ; Physics ; Mathematics |
| 源URL | [http://ir.itp.ac.cn/handle/311006/23643]  |
| 专题 | SCI会议论文 |
| 作者单位 | Chinese Acad Sci, Inst Theoret Phys, Key Lab Frontiers Theoret Phys, Beijing 100190, Peoples R China |
| 推荐引用方式 GB/T 7714 | Zhou, HJ. Solution space heterogeneity of the random K-satisfiability problem: Theory and simulations[C]. 见:. Kyoto Univ, Kyoto, JAPAN. MAR 07-10, 2010. |
入库方式： OAI收割
来源：理论物理研究所
浏览0
下载0
收藏0
其他版本
除非特别说明，本系统中所有内容都受版权保护，并保留所有权利。