I come from a background in statistical mechanics (not algorithm design or complexity theory), and the following question occurred to me that I could use some expert help in beginning to understand. The question is the following:

Given a statistical mechanics model for which I can find a closed-form for the partition function in the thermodynamic limit, does there exist an efficient algorithm for computing the partition function for a finite size analogue of said problem? By efficient, I mean an algorithm whose run time scales like a polynomial in the system size.

I'm aware that answering this question in generality would be extremely difficult, but my interest in the statement stems from the fact that I can't think of any examples in support of or against it, namely due to my inexperience with complexity theory. For example, we can write down the partition function for the 2D classical Ising model; does there exist an efficient algorithm for obtaining the partition function for the 2D Ising model with $N$ sites? In this case, my intuition says this should be the case, but I'm not sure! For more complicated models, I'm even less sure!

If anyone can offer examples for or counterexamples against this statement to I'd like to hear them, just for my own edification.

  • $\begingroup$ 2D Ising model with periodic boundary conditions can be solved exactly. $\endgroup$ Commented Apr 18, 2017 at 0:30
  • $\begingroup$ Yes but can it be solved efficiently? A naive algorithm would require an exponential number of operations to sum over all of the energy levels. $\endgroup$
    – miggle
    Commented Apr 18, 2017 at 0:42
  • $\begingroup$ The usual case with computational problems is that you do as much reduction by hand as possible (with an eye on leaving the remaining work computationally tractable, which sometimes means a slightly different approach that heading towards a closed solution), so problems with complete white-board solutions are only done computationally when they are the solvable subset of a more-difficult class. That is, they are done as part of validating a code, but not for their own sake. $\endgroup$ Commented Apr 18, 2017 at 1:00
  • $\begingroup$ Summing over all the states is wickedly expensive, so unless you're planning on working with a VERY small number of spins, this isn't going to work. The typical way to find the partition function is to run a Monte Carlo on your parameter space, compute enough observables to construct the partial derivatives of the partition function, and then integrate. That too can be costly, since your sims will have to run for pretty long to capture the observables near the critical point(s). $\endgroup$ Commented Apr 18, 2017 at 1:10
  • $\begingroup$ For the 2D Ising model the number of terms you need to sum over to compute the free energy, is just the number of spins. That summation becomes an integral in the limit of an infinite lattice. $\endgroup$ Commented Apr 18, 2017 at 1:27


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.