The grammar of the Ising model: a new complexity hierarchy

How complex is an Ising model? Usually, this is measured by the computational complexity of its ground state energy problem. Yet, this complexity measure only distinguishes between planar and non-planar interaction graphs, and thus fails to capture properties such as the average node degree, the number of long range interactions or the dimensionality of the lattice. Herein, we introduce a new complexity measure for Ising models and thoroughly classify Ising models with respect to it. Specifically, given an Ising model we consider the decision problem corresponding to the function graph of its Hamiltonian, and classify this problem in the Chomsky hierarchy. We prove that the language of this decision problem is (i) regular if and only if the Ising model is finite, (ii) constructive context free if and only if the Ising model is linear and its edge language is regular, (iii) constructive context sensitive if and only if the edge language of the Ising model is context sensitive, and (iv) decidable if and only if the edge language of the Ising model is decidable. We apply this theorem to show that the one-dimensional Ising model, the Ising model on generalized ladder graphs and the Ising model on layerwise complete graphs are constructive context free, while the two-dimensional Ising model, the all-to-all Ising model, and the Ising model on perfect binary trees are constructive context sensitive. This work is a first step in the characterization of physical interactions in terms of grammars.