What does one mean by heuristic statistical physics arguments?

Question

I have heard that there are heuristic arguments in statistical physics that yield results in probability theory for which rigorous proofs are either unknown or very difficult to arrive at. What is a simple toy example of such a phenomenon?

It would be good if the answer assumed little background in statistical physics and could explain what these mysterious heuristics are and how they can be informally justified. Also, perhaps someone can indicate the broad picture of how much of these heuristics can be rigorously justified and how the program of Lawler, Schramm and Werner fits into this.

Answer 1

The second paragraph of RJK's response deserves more detail.

Let $\phi$ be a formula in conjunctive normal form, with m clauses, n variables, and at most k variables per clause. Suppose we want to determine if $\phi$ has a satisfying assignment. Formula $\phi$ is an instance of the k-SAT decision problem.

When there are few clauses (so m is quite small compared to n), then it is almost always possible to find a solution. A simple algorithm will find a solution in roughly linear time in the size of the formula.

When there are many clauses (so m is quite large compared to n), then it is almost always the case that there is no solution. This can be shown by a counting argument. However, during search it is almost always possible to prune large parts of the search space by means of consistency techniques, because the many clauses interact so extensively. Establishing unsatisfiability can then usually be done efficiently.

• V. Chvátal and B. Reed. Mick gets some (the odds are on his side), FOCS 1992. doi: 10.1109/SFCS.1992.267789

In 1986 Fu and Anderson conjectured a relationship between optimisation problems and statistical physics, based on spin glass systems. Although they used sentences like

Intuitively, the system must be sufficiently large, but it is difficult to be more specific.

they do actually give specific predictions.

• Y Fu and P W Anderson. Application of statistical mechanics to NP-complete problems in combinatorial optimisation, J. Phys. A. 19 1605, 1986. doi: 10.1088/0305-4470/19/9/033

Based on arguments from statistical physics, Zecchina and collaborators conjectured that k-SAT should become hard when $\alpha = m/n$ is near a critical value. The precise critical value depends on k, but is in the region of 3.5 to 4.5 for 3-SAT.

• Rémi Monasson, Riccardo Zecchina, Scott Kirkpatrick, Bart Selman, Lidror Troyansky. Determining computational complexity from characteristic `phase transitions', Nature 400 133–137, 1999. (doi: 10.1038/22055 , free version)

Friedgut provided a rigorous proof of these heuristic arguments. For every fixed value of k, there are two thresholds $\alpha_1 < \alpha_2$. For $\alpha$ below $\alpha_1$, there is a satisfying assignment with high probability. For a value of $\alpha$ above $\alpha_2$, formula $\phi$ is unsatisfiable with high probability.

• Ehud Friedgut (with an appendix by Jean Bourgain), Sharp thresholds of graph properties, and the $k$-sat problem, J. Amer. Math. Soc. 12 1017–1054, 1999. (PDF)

Dimitris Achlioptas worked on many of the remaining issues, and showed that the above argument holds for constraint satisfaction problems, too. These are allowed to use more than just two values for each variable. One key paper shows rigorously why the Survey Propagation algorithm works so well to solve random k-SAT instances.

• A. Braunstein, M. Mézard, R. Zecchina, Survey propagation: An algorithm for satisfiability, Random Structures & Algorithms 27 201–226, 2005. doi: 10.1002/rsa.20057
• D. Achlioptas and F. Ricci-Tersenghi, On the Solution-Space Geometry of Random Constraint Satisfaction Problems, STOC 2006, 130–139. (preprint)

Answer 2

There is a very recent survey by Lawler on SLEs. You'll need to know a bit of complex analysis.

Although not directly related to your question, perhaps you could check out a few of Achlioptas' papers which also fit under the umbrella of "formalising physicists' heuristics", although from the viewpoint of a theoretical computer scientist. Or perhaps deeper into the statphys perspective you could browse through some of Zecchina's work.

I think it is worth adding that what you have referred to as physicists' "results" -- most of which should be called conjectures -- in this very broad category of problems rely almost as much (or even more) on numerical experiments as (than) on heuristic arguments.

Answer 3

(expnanding on my comment)

The "physical intuition" behind statistical methods, as used in computation, is Maximum Entropy (a-la Jaynes) plus associated stochastic methods like Simulated Annealing or Deterministic Annealing. Jaynes formulated the maximum entropy approach (a direct generalization of the statistical physics), to tackle inverse problems (in computational terms these include $NP$-hard problems)

A survey of "heuristics from nature" can be found here (circa 95)

Other heuristics involve generalised langrangians (aka primal-dual/expectation-maximization algorithms)

However these do not exhaust all "heuristics from nature" as in fact from 2003 onwards new heuristics based on electromargnetism have been used to tackle both continous and discrete/combinatorial optimization methods (like the multidimensional knapsack, or the TSP, circa 2012)