Mapping between Spin-Glass Three-Dimensional (3D) Ising Model and Boolean Satisfiability Problem

doi:10.3390/math11010237

IMR OpenIR

	Mapping between Spin-Glass Three-Dimensional (3D) Ising Model and Boolean Satisfiability Problem
	Zhang, Zhidong
通讯作者	Zhang, Zhidong(zdzhang@imr.ac.cn)
	2023
发表期刊	MATHEMATICS
卷号	11 期号:1 页码:13
摘要	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.
关键词	spin-glass 3D Ising model Boolean satisfiability computational complexity topology
资助者	National Natural Science Foundation of China
DOI	10.3390/math11010237
收录类别	SCI
语种	英语
资助项目	National Natural Science Foundation of China ; [52031014]
WOS研究方向	Mathematics
WOS类目	Mathematics
WOS记录号	WOS:000919443600001
出版者	MDPI
引用统计	被引频次：9[WOS] [WOS记录] [WOS相关记录]
文献类型	期刊论文
条目标识符	http://ir.imr.ac.cn/handle/321006/175312
专题	中国科学院金属研究所
通讯作者	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.