Qu'entend-on par arguments de physique statistique heuristique?

29

J'ai entendu dire qu'il existe des arguments heuristiques en physique statistique qui donnent des résultats dans la théorie des probabilités pour lesquels des preuves rigoureuses sont inconnues ou très difficiles à obtenir. Quel est un simple exemple de jouet d'un tel phénomène?

Ce serait bien si la réponse supposait peu de connaissances en physique statistique et pourrait expliquer ce que sont ces heuristiques mystérieuses et comment elles peuvent être justifiées de manière informelle. De plus, peut-être que quelqu'un peut donner une vue d'ensemble de la quantité de ces heuristiques qui peuvent être rigoureusement justifiées et comment le programme de Lawler, Schramm et Werner s'inscrit dans ce cadre.

Arnab
la source
Toutes mes excuses à l'avance pour la nature «débutante» de cette question!
arnab
1
J'avais une question similaire - par exemple, une formule pour le taux de croissance du nombre de promenades auto-évitantes sur un réseau 4d est justifiée par une "approche de groupe de renormalisation" même s'il n'y a pas de preuve rigoureuse
Yaroslav Bulatov
l'entropie maximale (a-la Jaynes et relations associées) est l'une des plus utilisées (d'une manière ou d'une autre)
Nikos M.

Réponses:

22

Le deuxième paragraphe de la réponse de RJK mérite plus de détails.

Soit une formule sous forme normale conjonctive, avec m clauses, n variables et au plus k variables par clause. Supposons que nous voulons déterminer si ϕ a une affectation satisfaisante. La formule ϕ est une instance du problème de décision k-SAT.ϕϕϕ

Lorsqu'il y a peu de clauses (donc m est assez petit par rapport à n), alors il est presque toujours possible de trouver une solution. Un algorithme simple trouvera une solution en un temps à peu près linéaire dans la taille de la formule.

Lorsqu'il y a beaucoup de clauses (donc m est assez grand par rapport à n), alors il est presque toujours vrai qu'il n'y a pas de solution. Cela peut être démontré par un argument de comptage. Cependant, au cours de la recherche, il est presque toujours possible d'élaguer de grandes parties de l'espace de recherche au moyen de techniques de cohérence, car les nombreuses clauses interagissent de manière très étendue. L'établissement de l'insatisfiabilité peut alors généralement se faire efficacement.

En 1986, Fu et Anderson ont conjecturé une relation entre les problèmes d'optimisation et la physique statistique, basée sur des systèmes de verre de spin. Bien qu'ils aient utilisé des phrases comme

Intuitivement, le système doit être suffisamment volumineux, mais il est difficile d'être plus précis.

ils donnent en fait des prédictions spécifiques.

  • Y Fu et PW Anderson. Application de la mécanique statistique aux problèmes NP-complets en optimisation combinatoire , J. Phys. A. 19 1605, 1986. doi: 10.1088 / 0305-4470 / 19/9/033

α=m/n

  • Rémi Monasson, Riccardo Zecchina, Scott Kirkpatrick, Bart Selman, Lidror Troyansky. Détermination de la complexité de calcul à partir des «transitions de phases» caractéristiques , Nature 400 133–137, 1999. ( doi: 10.1038 / 22055 , version gratuite )

α1<α2αα1αα2ϕ

  • k

Dimitris Achlioptas a travaillé sur bon nombre des problèmes restants et a montré que l'argument ci-dessus vaut également pour les problèmes de satisfaction des contraintes. Ceux-ci sont autorisés à utiliser plus de deux valeurs pour chaque variable. Un article clé montre rigoureusement pourquoi l'algorithme de propagation de l'enquête fonctionne si bien pour résoudre des instances aléatoires de k-SAT.

  • A. Braunstein, M. Mézard, R. Zecchina, propagation de l'enquête: un algorithme pour la satisfiabilité , structures et algorithmes aléatoires 27 201–226, 2005. doi: 10.1002 / rsa.20057
  • D. Achlioptas et F. Ricci-Tersenghi, Sur la géométrie de l'espace de solution des problèmes de satisfaction de contraintes aléatoires , STOC 2006, 130–139. ( préimpression )
András Salamon
la source
Merci pour les références! J'accepte cette réponse car elle est la plus complète. Je serais toujours intéressé par une description informelle du programme de Lawler, Schramm et Werner.
arnab
11

Il y a une enquête très récente de Lawler sur les LED . Vous aurez besoin de connaître un peu d'analyse complexe.

Bien que n'étant pas directement lié à votre question, vous pouvez peut-être consulter quelques articles d' Achlioptas qui s'inscrivent également dans le cadre de la «formalisation des heuristiques des physiciens», bien que du point de vue d'un informaticien théorique. Ou peut-être plus profondément dans la perspective de Statphys, vous pouvez parcourir une partie du travail de Zecchina .

Je pense qu'il convient d'ajouter que ce que vous avez appelé les "résultats" des physiciens - dont la plupart devraient être appelés des conjectures - dans cette très large catégorie de problèmes dépendent presque autant (voire plus) d'expériences numériques que ( que) sur des arguments heuristiques.

RJK
la source
Merci pour le lien vers l'enquête! Pouvez-vous développer davantage ce que sont ces expériences de calcul? Quelles connaissances de la physique statistique sont utilisées? Je cherchais un exemple de jouet simple (par exemple, de la théorie de la percolation) où l'on pourrait faire de manière informelle un argument statistique basé sur la physique.
arnab
Fondamentalement, Monte Carlo / Expériences statistiques, qui sont également largement utilisées dans l'étude de la SAT et ont fortement pollinisé avec la direction de la théorie dans la région
vzn
2

(développant mon commentaire)

NP

Une enquête sur «l' heuristique de la nature » peut être trouvée ici (vers 95)

D'autres heuristiques impliquent des langrangiens généralisés (alias algorithmes primal-dual / attente-maximisation)

Cependant, celles-ci n'épuisent pas toutes les " heuristiques de la nature ", car en fait à partir de 2003, de nouvelles heuristiques basées sur l'électromargnetisme ont été utilisées pour s'attaquer aux méthodes d'optimisation continue et discrète / combinatoire (comme le sac à dos multidimensionnel ou le TSP , vers 2012).

Nikos M.
la source