4

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?

user40780
  • 249
  • 1
  • 9
  • 1
    This is a good question, but not for this site. Short response: saying that something is $NP$-complete is not the same as saying that it takes exponential time to solve, and does imply that the problem is in $NP$. –  Dec 04 '14 at 18:33
  • Isn't the definition that something is NP-complete being that it is NP and NP-hard? – user40780 Dec 04 '14 at 19:52
  • Yes, which is why I wrote that "saying that something is $NP$-complete . . . does imply that the problem is in $NP$." As to taking exponential time, $EXPTIME$ is not known to be equal to $NP$; in fact, "$EXPTIME=NP$" is known to imply "$P\not=NP$." As a matter of fact, it is generally conjectured that $EXPTIME$ is strictly larger than $NP$. So knowing that something is $NP$-complete in no way implies that it takes exponential time to solve deterministically. –  Dec 04 '14 at 21:08
  • Thank you for your patience, as it is in NP, then it could be solved in polynomial time by nondeterministic turing machine. My doubt is that, in polynomial time with respect to what, the size? – user40780 Dec 04 '14 at 21:19

1 Answers1

12

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.

  • Thank you for your response, so what Onsager is solving is an analytic solution of F=E-ST? But for (2), I think it shall be NP-hard because we need to enumerate 2^n configurations to get all the energies and then there are basically no polynomial time solution to check that it is correct. Isn't it? Thank you very much again. – user40780 Dec 04 '14 at 20:02