Computational complexity of spin-glass three-dimensional (3D) Ising model

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