2025/06/02 by Zhidong Zhang, Zhang, Zhidong · 2 citations
Physics and Astronomy · #Complex Network Analysis Techniques #FOS: Physical sciences #General Physics (physics.gen-ph) #Opinion Dynamics and Social Influence #Theoretical and Computational Physics
paper · doi:10.48550/arxiv.2506.02067
openalex publication_date 2025/06/02 · openalex created_date 2025/10/14 · openalex updated_date 2026/07/28
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(2mn). 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(2mn) by any algorithms, which is in subexponential time, superpolynomial.