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

Zhidong Zhang ()
Additional contact information
Zhidong Zhang: Shenyang National Laboratory for Materials Science, Institute of Metal Research, Chinese Academy of Sciences, 72 Wenhua Road, Shenyang 110016, China

Mathematics, 2023, vol. 11, issue 1, 1-13

Abstract: 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 ≥ 3 M SAT K ≥ 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 M SGI 3 D 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 M AMC 3 D 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 ≥ 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 C L M SGI 3 D is the computational complexity by brute force search of the AMC model C U M AMC 3 D , the lower bound of the computational complexity of the K-SAT problem for K ≥ 4 C L M SAT K ≥ 4 is the computational complexity by brute force search of the K-SAT problem for K = 3 C U M SAT K = 3 . Namely, C L M SAT K ≥ 4 = C L M SGI 3 D ≥ C U M AMC 3 D = C U M SAT K = 3 . All of them are in subexponential and superpolynomial. Therefore, the computational complexity of the K-SAT problem for K ≥ 4 cannot be reduced to that of the K-SAT problem for K < 3.

Keywords: spin-glass 3D Ising model; Boolean satisfiability; computational complexity; topology (search for similar items in EconPapers)
JEL-codes: C (search for similar items in EconPapers)
Date: 2023
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
https://www.mdpi.com/2227-7390/11/1/237/pdf (application/pdf)
https://www.mdpi.com/2227-7390/11/1/237/ (text/html)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:gam:jmathe:v:11:y:2023:i:1:p:237-:d:1023284

Access Statistics for this article

Mathematics is currently edited by Ms. Emma He

More articles in Mathematics from MDPI
Bibliographic data for series maintained by MDPI Indexing Manager ().