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

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 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 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 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 Z2 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.

References in corpus (15)

• The random K-satisfiability problem: from an analytic solution to an efficient algorithm
• Clustering of solutions in the random satisfiability problem
• Statistical mechanics of the random K-SAT model
• Phase Transition in the Number Partitioning Problem
• The Entropy of the K-Satisfiability Problem
• A variational description of the ground state structure in random satisfiability problems
• Simplest random K-satisfiability problem
• Conjectures on exact solution of three - dimensional (3D) simple orthorhombic Ising lattices
• Clifford algebra approach of 3D Ising model
• Computational complexity of spin-glass three-dimensional (3D) Ising model
• Mathematical structure of three - dimensional (3D) Ising model
• Exact solution of two-dimensional (2D) Ising model with a transverse field: a low-dimensional quantum spin system
• Comment on "Conjectures on exact solution of three-dimensional (3D) simple orthorhombic Ising lattices" [arXiv:0705.1045]
• Three-Dimensional Ising Model and Transfer Matrices
• Topological Quantum Statistical Mechanics and Topological Quantum Field Theories

Cited by in corpus (5)

• Lower bound of computational complexity of knapsack problems
• Exact solution of the three-dimensional (3D) Z2 lattice gauge theory
• Hyperoptimized approximate contraction of tensor networks for rugged-energy-landscape spin glasses on periodic square and cubic lattices
• Exact solution of a two-dimensional (2D) Ising model with the next nearest interactions
• Equivalence between the zero distributions of the Riemann zeta function and a two-dimensional Ising model with randomly distributed competing interactions