<p>There is a <a href="http://pims2010.web.officelive.com/Documents/notes_Lawler.pdf">very recent survey by Lawler on SLEs</a>.  You'll need to know a bit of complex analysis.</p>

<p>Although not directly related to your question, perhaps you could check out a few of <a href="http://users.soe.ucsc.edu/~optas/">Achlioptas' papers</a> 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 <a href="http://users.ictp.it/~zecchina/selected_papers.html">Zecchina's work</a>.</p>

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

CC BY-SA 3.0
2012-08-03T20:14:28.550Z
basically, monte carlo/statistical experiments, which are also used heavily in the study of SAT and have crosspollinated heavily with the direction of theory in the area
vzn
CC BY-SA 2.5
2010-09-12T01:01:15.653Z
Thanks for the link to the survey! Can you expand more on what these computational experiments are?  What insights from statistical physics are used?  I was looking for a simple toy example (say, from percolation theory) where one could informally make a statistical physics-based argument.
arnab
CC BY-SA 2.5
2010-09-10T12:16:43.873Z
2010-09-10T12:16:43.873Z
RJK
<p>(expnanding on my comment)</p>

<p>The "physical intuition" behind statistical methods, as used in computation, is <a href="http://en.wikipedia.org/wiki/Maximum_entropy_thermodynamics" rel="nofollow">Maximum Entropy</a> (a-la Jaynes) plus associated stochastic methods like <a href="http://en.wikipedia.org/wiki/Simulated_annealing" rel="nofollow">Simulated Annealing</a> or <a href="http://www.google.gr/url?sa=t&amp;rct=j&amp;q=&amp;esrc=s&amp;source=web&amp;cd=7&amp;ved=0CF4QFjAG&amp;url=http%3A%2F%2Fwww.researchgate.net%2Fpublication%2F2382666_Pairwise_Data_Clustering_by_Deterministic_Annealing%2Ffile%2Fd912f50c75945d835b.pdf&amp;ei=FQulU5rxH8G2O9vFgfAL&amp;usg=AFQjCNGms38_X5574saoUmoG9fY1Suwrdw&amp;bvm=bv.69411363,d.ZWU&amp;cad=rja" rel="nofollow">Deterministic Annealing</a>. Jaynes formulated the maximum entropy approach (a direct <em>generalization</em> of the statistical physics), to tackle <em>inverse problems</em> (in computational terms these include $NP$-hard problems)</p>

<p>A survey of "<em>heuristics from nature</em>" can be found <a href="http://faculty.washington.edu/paymana/swarm/colorni96-itor.pdf" rel="nofollow">here</a> (circa 95)</p>

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

<p>However these do <strong>not</strong> exhaust all "<em>heuristics from nature</em>" as in fact from 2003 onwards <a href="http://www.ise.ncsu.edu/fangroup/ie789.dir/pub2.pdf" rel="nofollow">new heuristics based on electromargnetism</a> have been used to tackle both continous and discrete/combinatorial optimization methods (like the <a href="http://goanna.cs.rmit.edu.au/~xiaodong/publications/knapsack-bonyadi-li-2012.PDF" rel="nofollow">multidimensional knapsack</a>, or the <a href="http://www.inf.ucv.cl/~rsoto/cursos/MII748/EM/EM_paper_bin.pdf" rel="nofollow">TSP</a>, circa 2012)</p>

CC BY-SA 3.0
2014-06-21T04:32:51.233Z
2014-06-21T04:32:51.233Z
Nikos M.
<p>The second paragraph of RJK's response deserves more detail.</p>

<p>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.</p>

<p>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.</p>

<p>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.</p>

<ul>
<li>V. Chvátal and B. Reed. <em>Mick gets some (the odds are on his side)</em>, FOCS 1992. <a href="http://dx.doi.org/10.1109/SFCS.1992.267789">doi: 10.1109/SFCS.1992.267789</a></li>
</ul>

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

<blockquote>
  <p>Intuitively, the system must be sufficiently large, but it is difficult to be more specific.</p>
</blockquote>

<p>they do actually give specific predictions.</p>

<ul>
<li>Y Fu and P W Anderson. <em>Application of statistical mechanics to NP-complete problems in combinatorial optimisation</em>, J. Phys. A. <strong>19</strong> 1605, 1986. <a href="http://dx.doi.org/10.1088/0305-4470/19/9/033">doi: 10.1088/0305-4470/19/9/033</a> </li>
</ul>

<p>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.</p>

<ul>
<li>Rémi Monasson, Riccardo Zecchina, Scott Kirkpatrick, Bart Selman, Lidror Troyansky.  <em>Determining computational complexity from characteristic `phase transitions'</em>, Nature <strong>400</strong> 133–137, 1999.  (<a href="http://dx.doi.org/10.1038/22055">doi: 10.1038/22055</a> , <a href="http://www.phys.ens.fr/~monasson/Articles/a25.pdf">free version</a>)</li>
</ul>

<p>Friedgut provided a rigorous proof of these heuristic arguments.  For every fixed value of k, there are two thresholds $\alpha_1 &lt; \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.</p>

<ul>
<li>Ehud Friedgut (with an appendix by Jean Bourgain), <em>Sharp thresholds of graph properties, and the $k$-sat problem</em>, J. Amer. Math. Soc. <strong>12</strong> 1017–1054, 1999. (<a href="http://www.ams.org/journals/jams/1999-12-04/S0894-0347-99-00305-7/S0894-0347-99-00305-7.pdf">PDF</a>)</li>
</ul>

<p>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.</p>

<ul>
<li>A. Braunstein, M. Mézard, R. Zecchina, <em>Survey propagation: An algorithm for satisfiability</em>, Random Structures &amp; Algorithms <strong>27</strong> 201–226, 2005. <a href="http://dx.doi.org/10.1002/rsa.20057">doi: 10.1002/rsa.20057</a></li>
<li>D. Achlioptas and F. Ricci-Tersenghi, <em>On the Solution-Space Geometry of Random Constraint Satisfaction Problems</em>,
STOC 2006, 130–139. (<a href="http://users.soe.ucsc.edu/~optas/papers/fp68-achlioptas.pdf">preprint</a>)</li>
</ul>

CC BY-SA 2.5
2010-09-17T23:19:22.717Z
Thank you for the references!  I'm accepting this answer as it's the most comprehensive.  I'd still be interested in an informal description of the program of Lawler, Schramm, & Werner though.
arnab
CC BY-SA 2.5
2010-09-13T02:33:42.373Z
2010-09-13T13:01:16.397Z
2010-09-13T13:01:16.397Z
András Salamon
<p>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?</p>

<p>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.</p>

CC BY-SA 3.0
2014-06-21T04:15:35.590Z
[maximum entropy](http://en.wikipedia.org/wiki/Maximum_entropy_thermodynamics) (a-la Jaynes and associated relations) is one most used (in one way or the other)
Nikos M.
CC BY-SA 2.5
2010-09-10T05:44:59.210Z
Apologies in advance for the 'beginner' nature of this question!
arnab
CC BY-SA 2.5
2010-09-18T18:11:44.203Z
I had a similar question -- for instance, a formula for growth rate of the number of self-avoiding walks on 4d lattice is justified through "renormalization group approach" even though there's no rigorous proof
Yaroslav Bulatov
<sat><pr.probability><physics><statistical-physics>
What does one mean by heuristic statistical physics arguments?
arnab
# What does one mean by heuristic statistical physics arguments?

(Asked by: username_0 on 2010-09-10)

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.

**Tags:** sat, pr.probability, physics, statistical-physics
> **Comments:**
> **username_0**: Apologies in advance for the 'beginner' nature of this question!  
> **username_2**: I had a similar question -- for instance, a formula for growth rate of the number of self-avoiding walks on 4d lattice is justified through "renormalization group approach" even though there's no rigorous proof  
> **username_1**: [maximum entropy](http://en.wikipedia.org/wiki/Maximum_entropy_thermodynamics) (a-la Jaynes and associated relations) is one most used (in one way or the other)  

---

## 3 answers

### Answer by username_5 on 2010-09-13. Score: 22 | Accepted answer

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](http://dx.doi.org/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](http://dx.doi.org/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](http://dx.doi.org/10.1038/22055) , [free version](http://www.phys.ens.fr/~monasson/Articles/a25.pdf))

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](http://www.ams.org/journals/jams/1999-12-04/S0894-0347-99-00305-7/S0894-0347-99-00305-7.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](http://dx.doi.org/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](http://users.soe.ucsc.edu/~optas/papers/fp68-achlioptas.pdf))

> **Comments:**
> **username_0**: Thank you for the references!  I'm accepting this answer as it's the most comprehensive.  I'd still be interested in an informal description of the program of Lawler, Schramm, & Werner though.  

---

### Answer by username_3 on 2010-09-10. Score: 11

There is a [very recent survey by Lawler on SLEs](http://pims2010.web.officelive.com/Documents/notes_Lawler.pdf). 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](http://users.soe.ucsc.edu/~optas/) 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](http://users.ictp.it/~zecchina/selected_papers.html).

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.

> **Comments:**
> **username_0**: Thanks for the link to the survey! Can you expand more on what these computational experiments are?  What insights from statistical physics are used?  I was looking for a simple toy example (say, from percolation theory) where one could informally make a statistical physics-based argument.  
> **username_4**: basically, monte carlo/statistical experiments, which are also used heavily in the study of SAT and have crosspollinated heavily with the direction of theory in the area  

---

### Answer by username_1 on 2014-06-21. Score: 2

(expnanding on my comment)

The "physical intuition" behind statistical methods, as used in computation, is [Maximum Entropy](http://en.wikipedia.org/wiki/Maximum_entropy_thermodynamics) (a-la Jaynes) plus associated stochastic methods like [Simulated Annealing](http://en.wikipedia.org/wiki/Simulated_annealing) or [Deterministic Annealing](http://www.google.gr/url?sa=t&rct=j&q=&esrc=s&source=web&cd=7&ved=0CF4QFjAG&url=http%3A%2F%2Fwww.researchgate.net%2Fpublication%2F2382666_Pairwise_Data_Clustering_by_Deterministic_Annealing%2Ffile%2Fd912f50c75945d835b.pdf&ei=FQulU5rxH8G2O9vFgfAL&usg=AFQjCNGms38_X5574saoUmoG9fY1Suwrdw&bvm=bv.69411363,d.ZWU&cad=rja). 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](http://faculty.washington.edu/paymana/swarm/colorni96-itor.pdf) (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](http://www.ise.ncsu.edu/fangroup/ie789.dir/pub2.pdf) have been used to tackle both continous and discrete/combinatorial optimization methods (like the [multidimensional knapsack](http://goanna.cs.rmit.edu.au/~xiaodong/publications/knapsack-bonyadi-li-2012.PDF), or the [TSP](http://www.inf.ucv.cl/~rsoto/cursos/MII748/EM/EM_paper_bin.pdf), circa 2012)


---

