Computational complexity of spin-glass three-dimensional (3D) Ising model
arXiv:2506.02067 · doi:10.1016/j.jmst.2019.12.009
Abstract
In this work, the computational complexity of a spin-glass three-dimensional (3D) Ising model (for the lattice size N = lmn, where l, m, n are the numbers of lattice points along three crystallographic directions) is studied. We prove that an absolute minimum core (AMC) model consisting of a spin-glass 2D Ising model interacting with its nearest neighboring plane, has its computational complexity O(2^mn). Any algorithms to make the model smaller (or simpler) than the AMC model will cut the basic element of the spin-glass 3D Ising model and lost many important information of the original model. Therefore, the computational complexity of the spin-glass 3D Ising model cannot be reduced to be less than O(2^mn) by any algorithms, which is in subexponential time, superpolynomial.
21 pages, 0 figure
References in corpus (6)
- The Thermodynamic Limit in Mean Field Spin Glass Models
- General properties of overlap probability distributions in disordered spin systems. Toward Parisi ultrametricity
- Conjectures on exact solution of three - dimensional (3D) simple orthorhombic Ising lattices
- Clifford algebra approach of 3D Ising model
- Comment on "Conjectures on exact solution of three-dimensional (3D) simple orthorhombic Ising lattices" [arXiv:0705.1045]
- Three-Dimensional Ising Model and Transfer Matrices
Cited by in corpus (11)
- Exact solution of two-dimensional (2D) Ising model with a transverse field: a low-dimensional quantum spin system
- Mapping between Spin-Glass Three-Dimensional (3D) Ising Model and Boolean Satisfiability Problem
- Topological Quantum Statistical Mechanics and Topological Quantum Field Theories
- Dynamic Asset Allocation with Expected Shortfall via Quantum Annealing
- Lower bound of computational complexity of knapsack problems
- Computational complexity of three-dimensional Ising spin glass: Lessons from D-Wave annealer
- Computational Characteristics of Random Field Ising Model with Long-Range Interaction
- Exact solution of the three-dimensional (3D) Z2 lattice gauge theory
- Eigenmodes of a disordered FeCo magnonic crystal at finite temperatures
- 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