NP-completeness of Ising model

Question

In this paper: http://www.brown.edu/Research/Istrail_Lab/papers/p87-istrail.pdf

It is claimed that calculating partition function of 3 dimensional ising model is NP-complete. But I have a question, is it saying that calculating partition function is exponential with respect to the size of lattice? But generally in physics, I think people is interested in the partition function of an infinite system, not some finite system. And that exponentiation shall not preclude the chance of getting partition function infinite 3D systems, right?

Second question: From complexity theory class that I self taught, one problem is called NP-complete only if the solution could be verify in polynomial time. So is it true that one could give a partition function for a finite 3D Ising system with a certificate which can be checked in polynomial time?

Third question: If I am not wrong, I consider the ground state problem of 3D Ising problem to be NP-hard and not NP, right?

Answer 1

There are three quite separate problems:

1. Find a ground state of an Ising model on a finite graph with couplings in, say, $\{-1,0,1\}$.
2. Find the partition function of such an Ising model, as a function of inverse temperature.
3. Find the infinite-volume limit of the free energy of an Ising model with translation-invariant or periodic interaction.

(3) is the problem Onsager solved in "closed form" for the two-dimensional ferromagnet. As far as we know, the corresponding three-dimensional problem does not have a closed form.

The partition function in (2) is essentially a polynomial of degree $O(n)$ where $n$ is the number of sites, whose coefficients give the number of configurations of each possible energy. Since calculating the energy of a given configuration is easy, computing the partition function is in #P, not (as far as we know) NP.

(1) (or rather the corresponding decision problem, "Is there a state of energy $\le k$?") is NP-complete in general.

Physicists used to be interested mainly in infinite systems, but that is no longer the case.

EDIT: Counting the number of ground states is #P-complete, and therefore so is (2). Note that even in cases where finding a ground state is easy, counting the number of ground states can be hard. The classic example is perfect matchings in bipartite graphs. This can be formulated as an Ising problem (on a graph whose vertices correspond to the edges of the bipartite graph). Deciding whether a perfect matching exists is in P, but counting the number of perfect matchings is #P-complete.