Maximally flexible solutions of a random K-satisfiability formula
文献类型：期刊论文
| 作者 | Zhao, Han; Zhou, Hai -Jun |
| 刊名 | PHYSICAL REVIEW E
 |
| 出版日期 | 2020 |
| 卷号 | 102期号:1页码:12301 |
| 关键词 | SURVEY PROPAGATION ALGORITHM THRESHOLD SAT |
| ISSN号 | 2470-0045 |
| DOI | 10.1103/PhysRevE.102.012301 |
| 英文摘要 | Random K-satisfiability (K-SAT) is a paradigmatic model system for studying phase transitions in constraint satisfaction problems and for developing empirical algorithms. The statistical properties of the random K-SAT solution space have been extensively investigated, but most earlier efforts focused on solutions that are typical. Here we consider maximally flexible solutions which satisfy all the constraints only using the minimum number of variables. Such atypical solutions have high internal entropy because they contain a maximum number of null variables which are completely free to choose their states. Each maximally flexible solution indicates a dense region of the solution space. We estimate the maximum fraction of null variables by the replica-symmetric cavity method, and implement message-passing algorithms to construct maximally flexible solutions for single K-SAT instances. |
| 学科主题 | Physics |
| 语种 | 英语 |
| 源URL | [http://ir.itp.ac.cn/handle/311006/27393]  |
| 专题 | 理论物理研究所_理论物理所1978-2010年知识产出 |
| 作者单位 | Chinese Acad Sci, Inst Theoret Phys, CAS Key Lab Theoret Phys, Beijing 100190, Peoples R China; Univ Chinese Acad Sci, Sch Phys Sci, Beijing 100049, Peoples R China |
| 推荐引用方式 GB/T 7714 | Zhao, Han,Zhou, Hai -Jun. Maximally flexible solutions of a random K-satisfiability formula[J]. PHYSICAL REVIEW E,2020,102(1):12301. |
| APA | Zhao, Han,&Zhou, Hai -Jun.(2020).Maximally flexible solutions of a random K-satisfiability formula.PHYSICAL REVIEW E,102(1),12301. |
| MLA | Zhao, Han,et al."Maximally flexible solutions of a random K-satisfiability formula".PHYSICAL REVIEW E 102.1(2020):12301. |
入库方式： OAI收割
来源：理论物理研究所
浏览0
下载0
收藏0
其他版本
除非特别说明，本系统中所有内容都受版权保护，并保留所有权利。