Mapping between Spin-Glass Three-Dimensional (3D) Ising Model and Boolean Satisfiability Problem
文献类型：期刊论文
| 作者 | Zhang, Zhidong |
| 刊名 | MATHEMATICS
 |
| 出版日期 | 2023 |
| 卷号 | 11期号:1页码:13 |
| 关键词 | spin-glass 3D Ising model Boolean satisfiability computational complexity topology |
| DOI | 10.3390/math11010237 |
| 通讯作者 | Zhang, Zhidong(zdzhang@imr.ac.cn) |
| 英文摘要 | The common feature for a nontrivial hard problem is the existence of nontrivial topological structures, non-planarity graphs, nonlocalities, or long-range spin entanglements in a model system with randomness. For instance, the Boolean satisfiability (K-SAT) problems for K & GE; 3 MSATK & GE;3 are nontrivial, due to the existence of non-planarity graphs, nonlocalities, and the randomness. In this work, the relation between a spin-glass three-dimensional (3D) Ising model MSGI3D with the lattice size N = mnl and the K-SAT problems is investigated in detail. With the Clifford algebra representation, it is easy to reveal the existence of the long-range entanglements between Ising spins in the spin-glass 3D Ising lattice. The internal factors in the transfer matrices of the spin-glass 3D Ising model lead to the nontrivial topological structures and the nonlocalities. At first, we prove that the absolute minimum core (AMC) model MAMC3D exists in the spin-glass 3D Ising model, which is defined as a spin-glass 2D Ising model interacting with its nearest neighboring plane. Any algorithms, which use any approximations and/or break the long-range spin entanglements of the AMC model, cannot result in the exact solution of the spin-glass 3D Ising model. Second, we prove that the dual transformation between the spin-glass 3D Ising model and the spin-glass 3D Z(2) lattice gauge model shows that it can be mapped to a K-SAT problem for K & GE; 4 also in the consideration of random interactions and frustrations. Third, we prove that the AMC model is equivalent to the K-SAT problem for K = 3. Because the lower bound of the computational complexity of the spin-glass 3D Ising model CLMSGI3D is the computational complexity by brute force search of the AMC model CUMAMC3D, the lower bound of the computational complexity of the K-SAT problem for K & GE; 4 CLMSATK & GE;4 is the computational complexity by brute force search of the K-SAT problem for K = 3 CUMSATK=3. Namely, CLMSATK & GE;4=CLMSGI3D & GE;CUMAMC3D=CUMSATK=3. All of them are in subexponential and superpolynomial. Therefore, the computational complexity of the K-SAT problem for K & GE; 4 cannot be reduced to that of the K-SAT problem for K < 3. |
| 资助项目 | National Natural Science Foundation of China ; [52031014] |
| WOS研究方向 | Mathematics |
| 语种 | 英语 |
| 出版者 | MDPI |
| WOS记录号 | WOS:000919443600001 |
| 资助机构 | National Natural Science Foundation of China |
| 源URL | [http://ir.imr.ac.cn/handle/321006/175311]  |
| 专题 | 金属研究所_中国科学院金属研究所 |
| 通讯作者 | Zhang, Zhidong |
| 作者单位 | Chinese Acad Sci, Inst Met Res, Shenyang Natl Lab Mat Sci, 72 Wenhua Rd, Shenyang 110016, Peoples R China |
| 推荐引用方式 GB/T 7714 | Zhang, Zhidong. Mapping between Spin-Glass Three-Dimensional (3D) Ising Model and Boolean Satisfiability Problem[J]. MATHEMATICS,2023,11(1):13. |
| APA | Zhang, Zhidong.(2023).Mapping between Spin-Glass Three-Dimensional (3D) Ising Model and Boolean Satisfiability Problem.MATHEMATICS,11(1),13. |
| MLA | Zhang, Zhidong."Mapping between Spin-Glass Three-Dimensional (3D) Ising Model and Boolean Satisfiability Problem".MATHEMATICS 11.1(2023):13. |
入库方式： OAI收割
来源：金属研究所
浏览0
下载0
收藏0
其他版本
除非特别说明，本系统中所有内容都受版权保护，并保留所有权利。