Knowledge Management System of Institute of Theoretical Physics, CAS

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

Zhou, HJ
| |

2010 | |

Conference Name | International Workshop on Statistical-Mechanical Informatics 2010 (IW-SMI 2010) |

Source Publication | INTERNATIONAL WORKSHOP ON STATISTICAL-MECHANICAL INFORMATICS 2010 (IW-SMI 2010) |

Volume | 233 |

Pages | 12011 |

Conference Date | MAR 07-10, 2010 |

Conference Place | Kyoto Univ, Kyoto, JAPAN |

Author of Source | Kyoto Univ |

Publication Place | BRISTOL |

ISSN | 1742-6588 |

Publisher | IOP PUBLISHING LTD |

Abstract | 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. |

Keyword | CONSTRAINT SATISFACTION PROBLEMS SPIN-GLASSES MEAN-FIELD DYNAMICS LIQUIDS STATES |

DOI | 10.1088/1742-6596/233/1/012011 |

URL | 查看原文 |

Indexed By | CPCI |

Language | 英语 |

WOS Research Area | Computer Science ; Physics ; Mathematics |

WOS Subject | Computer Science, Theory & Methods ; Physics, Applied ; Statistics & Probability |

Citation statistics | |

Document Type | 会议论文 |

Identifier | http://ir.itp.ac.cn/handle/311006/23643 |

Collection | SCI会议论文 |

Affiliation | Chinese Acad Sci, Inst Theoret Phys, Key Lab Frontiers Theoret Phys, Beijing 100190, Peoples R China |

First Author Affilication | Institute of Theoretical Physics, Chinese Academy of Sciences |

Recommended CitationGB/T 7714 | Zhou, HJ. Solution space heterogeneity of the random K-satisfiability problem: Theory and simulations[C]//Kyoto Univ. BRISTOL:IOP PUBLISHING LTD,2010:12011. |

Files in This Item: |
| |||||

There are no files associated with this item. |

Items in the repository are protected by copyright, with all rights reserved, unless otherwise indicated.

## Edit Comment