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

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

Problem Statement
The paper addresses the computational complexity of the spin-glass three-dimensional (3D) Ising model, a fundamental problem in statistical physics that has remained unsolved for nearly a century. The author investigates the relationship between this physical model and the Boolean Satisfiability (K-SAT) problem, a central issue in combinatorial optimization and computer science. Specifically, the work seeks to determine if the spin-glass 3D Ising model can be mapped to K-SAT problems, identify the specific value of $K$ for this mapping, and establish the lower bounds of computational complexity for these systems. The core challenge lies in the non-trivial topological structures, non-planarity, non-localities, and long-range spin entanglements inherent in the 3D spin-glass system, which distinguish it from the solvable 2D ferromagnetic Ising model.

Methodology
The author employs a combination of algebraic, topological, and dual-transformation techniques to analyze the systems:

1. Clifford Algebra Representation: The paper utilizes Clifford algebra to represent the partition function and transfer matrices of the spin-glass 3D Ising model. This approach is used to explicitly reveal the existence of long-range entanglements between Ising spins, which arise from the internal factors of the transfer matrices. The author argues that these entanglements represent a non-local effect where nearest-neighbor interactions along the third dimension act as effective long-range interactions mediated by the entanglement of all spins within a plane.
2. Definition of the Absolute Minimum Core (AMC) Model: The author defines an "Absolute Minimum Core" (AMC) model, denoted as $M_{AMC}^{3D}$, as a spin-glass 2D Ising model interacting with its nearest neighboring plane. This model is posited as the fundamental element of spin entanglement in the full 3D system.
3. Dual Transformation: The study applies a dual transformation to map the spin-glass 3D Ising model to a spin-glass 3D $Z_2$ lattice gauge model. This transformation relates the two-spin link interactions of the Ising model to multi-spin plaquette interactions in the gauge model.
4. Complexity Analysis: The computational complexity is analyzed by comparing the lower bound of the spin-glass 3D Ising model ($C_L$) against the upper bound of the AMC model ($C_U$), calculated via brute-force search. The analysis considers the impact of randomness, frustration, and non-ergodic behavior.

Key Contributions and Results

• Existence of Long-Range Entanglement: The paper proves (Theorem 1) that long-range entanglements exist between Ising spins in the spin-glass 3D lattice, represented by exponential factors in the transfer matrices. These entanglements are a consequence of the 3D topology and cannot be broken without losing the exact solution.
• Necessity of the AMC Model: It is proven (Theorem 2) that any algorithm using approximations or breaking the long-range spin entanglements of the AMC model cannot yield the exact solution for the spin-glass 3D Ising model. Consequently, the lower bound of the computational complexity for the 3D model is at least the complexity of the brute-force search of the AMC model ($C_L(M_{SGI}^{3D}) \geq C_U(M_{AMC}^{3D})$).
• Mapping to K-SAT ($K \geq 4$): Through the dual transformation to the 3D $Z_2$ lattice gauge model, the paper establishes (Theorem 4) that the spin-glass 3D Ising model is equivalent to the Boolean satisfiability problem for $K \geq 4$ ($M_{SGI}^{3D} \Leftrightarrow M_{SAT}^{K \geq 4}$). The mapping accounts for random interactions and frustrations, where closed polygons of frustration in 3D may involve more than four spins, necessitating $K \geq 4$.
• Mapping of the AMC Model to 3-SAT: The paper demonstrates (Theorem 5) that the AMC model ($M_{AMC}^{3D}$), defined as a 2D plane interacting with a neighbor, is equivalent to the K-SAT problem for $K=3$ ($M_{AMC}^{3D} \Leftrightarrow M_{SAT}^{K=3}$). This is derived via a star-triangular duality relation.
• Complexity Lower Bounds: The central result (Theorem 6) links the complexities of these systems:
  $$C_L(M_{SAT}^{K \geq 4}) = C_L(M_{SGI}^{3D}) \geq C_U(M_{AMC}^{3D}) = C_U(M_{SAT}^{K=3})$$
  The paper concludes that the lower bound of the computational complexity for $K \geq 4$ is determined by the brute-force search complexity of the $K=3$ problem.
• Complexity Class: The computational complexity for these problems is identified as being in the subexponential and superpolynomial range (Theorem 8). The author asserts that the complexity of $K$-SAT for $K \geq 4$ cannot be reduced to that of $K$-SAT for $K < 3$.
• Borderline Status: The AMC model ($M_{AMC}^{3D}$) and the 3-SAT problem ($M_{SAT}^{K=3}$) are identified as the "border" between P-problems (like the 2D Ising model and 2-SAT) and NP-complete problems (like the 3D Ising model and $K \geq 4$ SAT). The paper notes the AMC model is NP-complete but cannot be reduced further to a P-problem.

Significance
The paper claims to provide a rigorous bridge between physics, mathematics, and computer science by establishing a direct mapping between the spin-glass 3D Ising model and the K-SAT problem. By utilizing Clifford algebra and dual transformations, the work elucidates the topological and non-local origins of the computational hardness in these systems. The primary significance lies in the proof that the computational complexity of the 3D spin-glass Ising model is fundamentally tied to the complexity of the 3-SAT problem (and by extension, $K$-SAT for $K \geq 4$). The author argues that this relationship demonstrates that the lower bound of complexity for these hard problems is subexponential and superpolynomial, reinforcing the difficulty of finding exact solutions for these systems without brute-force approaches on their core structures. The work aims to enhance the understanding of the mathematical structures underlying NP-complete problems and the physical mechanisms (such as long-range entanglement) that drive their intractability.