Parallèlement, plusieurs informaticiens ont montré que de nombreux problèmes de physique statistique (entropie du modèle d'Ising, verre de spin) se ramenaient à des problèmes d'optimisation combinatoire, qui se trouvent être NP-complets comme beaucoup d'autres problèmes provenant de la recherche opérationnelle ou d'autres applications. Pour ces problèmes, des techniques mises au point ces dernières années font appel à des algorithmes approchés ou probabilistes (le plus souvent en fait mêlant les deux approches). Elles permettent d'obtenir dans de nombreux cas un résultat satisfaisant, en ce sens que l'on peut démontrer rigoureusement que le résultat est, avec une forte probabilité, proche de l'optimum cherché. Un grand nombre de travaux dans ce domaine sont au coeur du développement actuel de l'algorithmique; le domaine de l'énumération approchée (approximate counting) est ainsi considéré comme l'un plus féconds dans cette direction. En retour, les résultats obtenus ont été appliqués plusieurs fois avec succès à des problèmes provenant de la physique. Les travaux de Kenyon (monomères-dimères) et Martin (couplage Euclidien, voyageur de commerce), membres de l'action, sont en particuliers représentatifs de cette approche.
Une domaine privilégié est l'aléa de la NP-complétude. Par exemple, des travaux récents (Mertens) suggèrent une structure très régulière du comportement probabiliste du problème ``Integer Partitioning'' (qui est NP-complet et est l'un des six problèmes fondamentaux du livre de Garey et Johnson), d'où des régularités statistiques attendues éventuellement exploitables d'un point de vue algorithmique (Karamarkar, Odlyzko, Karp). Le problème SAT (satisfiabilité d'expressions booléennes) donne lieu lui aussi a des phénomènes de seuil surprenants et encore mal compris: il semble bien que les formules ``difficiles'' se concentrent dans une zone très particulière de l'espace qu'il reste à ``cartographier''. Ce problème donne lieu a des approches complémentaires, soit probabilistes et combinatoires (travaux de De la Vega et Dubois), soit de type physique statistique (travaux de Monasson: fonctions de partitions et méthodes de répliques) dont le recouvrement n'est encore que très partiel.
Sur un autre registre, les opérateurs de transfert, originellement conçus pour fournir un cadre rigoureux à une large classe de systèmes de la thermodynamique statistique se sont avérés un outil de base pour les systèmes dynamiques. Ils viennent d'être introduits très efficacement pour quantifier l'aléa en analyse d'algorithmes dans des domaines variés et parfois surprenants (travaux de Vallée), comme les algorithmes ``semi-numeriques'' au sens de Knuth, les modèles de données non uniformes et les structures de données digitales de Bentley-Sedgewick, ou encore la théorie analytique de l'information.
Par ailleurs, les développements perturbatifs sont une source importante de séries qui possèdent très fréquemment une interpretation combinatoire naturelle. Dans ce contexte, le problème de comptage de marches autoevitantes qui est lié aux propriétés fondamentales de transitions de phase de systèmes physiques (ferromagnétisme) est un problème combinatoire qui demeure non résolu depuis une quarantaine d'années. Guttmann et l'École de Melbourne ont introduit un grand nombre de modèles approchés que les méthodes de combinatoire énumérative permettent d'aborder efficacement. La physique fournit ainsi une source importante de problèmes à l'analyse combinatoire dont les solutions (e.g., travaux de Bousquet-Mélou sur les polyominos et de Gouyou-Beauchamps sur la percolation dirigée) peuvent donner des indications qualitatives précieuses quant aux comportements attendus de systèmes actuellement réputés comme ``intractables''.
Enfin, les problèmes de graphes aléatoires qui interviennent dans l'étude de réseaux d'interconnection sont, à l'instar du problème SAT, approchables tant par l'analyse combinatoire (travaux de Flajolet, Knuth, Salvy, et al.) que par la physique statistique (travaux de Monasson). La comparaison précise des puissances de description des deux formalismes reste à faire; il s'agit là d'une question méthodologique d'un grand intérêt qui peut fort bien conduire en retour à une meilleure compréhension du problème SAT et dont les chances de succès sont grandes étant donné le caractère analytiquement et structurellement simple du modèle des graphes aléatoires.
De nombreuses rencontres auxquelles plusieurs d'entre nous ont
participé, parfois même en tant qu'organisateurs
(Allouche, Bousquet-Mélou, Monasson) ont eu lieu
ces
dernières années et ont contribué à rapprocher les différentes
communautés : citons par exemple une Ecole à Jerusalem en 1996 un
autre en 1997 à
Rutgers (DIMACS), diverses rencontres à Luminy dans le cadre du Cirm, deux
rencontres cet été à Los Alamos et à Toronto, enfin une
dernière en octobre 1998à Turin. Ce foisonnement
montre la dynamique incontestable du domaine et la réalité
d'une avancée scientifique en plein développement.
Cette action de coopération se propose de contribuer à une plus
grande cohérence dans les travaux menés par un accroissement des
collaborations entre diverses communautés :
Les thèmes de recherche, essentiellement motivés par l'attaque algorithmique de systèmes complexes, s'organisent en analyse et modéles d'une part, simulation et optimisation d'autre part.
Enumération (exacte ou asymptotique) d'objets tracés sur un réseau : Dans ce cadre on désigne sous le nom de réseau, une grille à maille carrée, triangulaire ou hexagonale. Un certain nombre de modèles de physique statistique (Ising, magnétisme, modèles de gaz, etc...) se ramènent à un problème combinatoire de comptage d'objets discrets dessinés sur un réseau, selon divers paramètres. Par exemple, il suffirait de compter certains sous ensembles finis du plan discret appelés animaux, pour résoudre exactement les modèles de percolation (mais ceci est considéré comme l'une des questions parmi les plus difficiles du domaine), et compter des animaux dirigés 3D équivaut à résoudre le modèle des hexagones durs (ce qui est possible mais peu aisé). Dans certains cas, ces objets sont intéressants par eux-mêmes (animaux vus comme modèles de polymères dans un solvant, chemins auto-évitants comme modèle non-markovien type...). Les objets mathématiques modélisent alors un ``objet physique'' qui interagit avec lui-même et le milieu extérieur (la forme d'un polymère dépend ainsi de la qualité du solvant).
Un premier objectif consiste à énumérer directement les objets en question. C'est vraisemblablement impossible dans certains cas (ex: compter exactement tous les chemins auto-évitants du réseau carré). D'où la nécessité de mettre en évidence des modèles plus simples mais qui rendent compte assez fidèlement de certaines propriétés du modèle initial.
Un second objectif consiste pour certains modèles déjà résolus, notamment ceux qui font intervenir ce qu'on appelle des q-séries, à obtenir des équivalents asymptotiques. Du point de vue de la physique, c'est souvent le rayon de convergence d'une série génératrice qui est significatif : s'il dépend d'un paramètre du modèle, les valeurs où elle cesse d'être analytique correspondent aux changements de phase du modèle. Egalement, par des techniques asymptotiques, on peut envisager l'étude de la distribution limite de certains paramètres (aire d'un polygone auto-évitant contraint de grand périmètre par exemple).
Parmi les q-séries qu'on a obtenues ces dernières années, une seule a fait l'objet d'un tel travail (Prellberg). Par ailleurs, Flajolet a obtenu des résultats partiels sur les lois limites correspondantes, qui paraissent être presque toujours des distributions d'Airy [7]. Bref, il y a un important domaine à considérer qui doit bénéficier des compétences en combinatoire énumérative des uns et de celles en matière de séries génératrices des autres.
Automate du Tas de Sable : Un automate cellulaire introduit en physique théorique dans le but de modéliser des phénomènes physiques de nature diverses (comme les avalanches, l'éboulement d'un tas de sable, les tremblements de terre), a donné lieu à des développements remarquables. Il s'agit de celui appelé tas de sable, on peut le représenter comme un graphe aux sommets valués par des entiers que l'on peut de manière imagée considérer comme des grains de sable. La fonction de transition de l'automate est constituée par une règle d'éboulement, consistant pour chaque sommet valué par un nombre supérieur à son degré à transférer un grain de sable sur chacun de ses voisins. Le résultat profond obtenu par D. Dhar (Tata, Bombay) est la mise en évidence d'une loi de groupe commutatif sur certaines configurations (configurations récurrentes) qui se trouvent être en bijection avec les arbres recouvrants du graphe sous-jacent. On obtient donc grâce à la modélisation d'un phénomène physique un résultat étonnant sur les graphes [3]. Réciproquement l'algorithmique des graphes doit permettre de traiter un certain nombre de questions sur la modélisation physique : détermination d'algorithmes efficaces permettant de calculer les éboulements successifs provoqués par des chutes de grains de sable, comparaison des algorithmes de génération aléatoire d'arbres recouvrants et ceux du calcul d'une configuration récurrente aléatoire, détermination de polynômes associés aux configurations. Un résultat récent relie de façon très mystérieuse le polynôme énumérateur des configurations récurrentes suivant leur poids au polynôme de Tutte du graphe sous-jacent, le calcul effectif de ces polynômes est ainsi à ajouter aux objectifs à atteindre.
Combinatoire analytique, opérateurs de transfert et analyse d'algorithmes : La combinatoire analytique se donne pour objectif l'exploitation systématique des propriétés analytiques de séries génératrices associées aux grands modéles de l'aléa discret. Ce domaine s'applique remarquablement bien à l'analyse en moyenne ou en probabilité des algorithmes et structures de données fondamentales. Nous proposons dans le cadre de cette action d'explorer deux voies prometteuses.
Tout d'abord, pour les problèmes de faible complexité, nous envisageaons de développer l'utilisation des opérateurs de transfert issus du formalisme thermodynamique (Ruelle) et qui jouent pour de nombreux problèmes un rôle d'opérateur génerateur analogue aux fonctions génératrices usuelles. Ces opérateurs de transfert permettent de prendre en compte des modèles à correlations non bornées donc non Markoviens. Dans le même temps, leur propriétés analytiques essentielles généralisent agréablement les transformations linéaires en dimension finie, d'où une grande transparence conceptuelle. Il est prévu d'en développer l'usage dans le domaine de la théorie analytique de l'information (modèles corrélés et structures d'arbres digitaux, hybrides ou non). De surcroît des succès récents (résolution de la conjecture de Brent datant de 1976 dans [11]) permettent d'en envisager l'application à des algorithmes itératifs, ce même en l'absence de préservation d'un ``aléa uniforme''.
Ensuite, pour les problèmes de plus haute complexité, nous
prévoyons de développer les méthodes de col
multidimensionnelles,
ce dans plusieurs directions: perturbations, cols coalescents, cols
hautement multidimensionnels.
(La théorie de l'holonomie multivariée en
conjonction avec les travaux récents de
Chyzak devrait aussi intervenir.)
Ceci passe par le traitement
d'intégrales multiples qui constituent par ailleurs un mode
classique de représentation des fonctions de partition en physique
statistique. Plusieurs faits indiquent le caractère prometteur d'une
tel approche. Par exemple, la connectivité des
graphes aléatoires est traitable
analytiquement par ces méthodes (travaux de Flajolet et Salvy,
voir [6]) et l'approche peut être comparée aux
heuristiques physiques (travaux Monasson). Par ailleurs, le fait que
les coûts moyens de divers problèmes d'optimisation s'expriment au
moyen de constantes classiques telles 
(couplages, arbres de recouvrement) donne confiance en la viabilité
de l'approche. L'intérêt de ces méthodes provient de ce que des
représentations intégrales voisines de celles utilisées en
physique permettent en principe la prise en compte analytique de contraintes
complexes (de type NP-complétude) dans les problèmes
combinatoires difficiles, comme le partitionnement d'entiers ou le problème
SAT.
Simulations numériques des systèmes complexes : Les simulations de Monte-Carlo sont un outil universel pour étudier le comportement à l'équilibre de modèles de physique statistique. Il s'agit de simuler une chaîne de Markov ergodique dont les états sont les configurations du système et dont la distribution stationnaire est la distribution de Gibbs.
On peut faire une estimation numérique précise de la valeur de diverses quantités importantes en observant la chaîne à l'état stationnaire. Il est alors primordial que la chaîne de Markov soit exécutée suffisamment longtemps pour être proche de l'état d'équilibre. Dans les faits, on utilise habituellement des méthodes ad hoc pour déterminer la longueur de la simulation. Cependant, des progrès récents en informatique et mathématiques discrètes permettent de calculer des bornes a priori sur le nombre de pas de la chaîne avant d'atteindre l'équilibre. Ces techniques ont récemment été appliquées à des simulations de Monte-Carlo pour certains modèles physiques, dont le modèle monomère-dimère [8], le modèle d'Ising, les marches auto-évitantes et le modèle à noyau dur [9]. Cependant, il reste beaucoup de travail à faire, pour l'amélioration de ces bornes pour exemples ci-dessus (bornes qui sont encore trop grandes pour être utiles en pratique), ou pour l'étude de nouvelles simulations plus complexes et donc probablement plus efficaces.
Mélange rapide, transitions de phase et génération aléatoire d'objets combinatoires: De nouveaux liens sont récemment apparus entre les dynamiques de certaines simulations de Monte Carlo, les ``dynamiques de Glauber'', et des phénomènes critiques. Par exemple, pour le modèle d'Ising, il a récemment été établi que la propriété de ``mélange rapide'' (c'est-à-dire de convergence rapide vers l'équilibre) des dynamiques de Glauber correspond à l'unicité de la mesure de Gibbs, et donc au fait que le système soit au delà d'un certain point critique. En d'autres termes, la transition de phase bien connue se manifeste par un passage d'une dynamique rapidement mélangeante à une dynamique mélangeant lentement (ce phénomène était observé depuis longtemps mais ce n'est que tout récemment qu'il a été rigoureusement justifié). Ceci ouvre la possibilité alléchante d'un nouveau lien entre l'étude classique des transitions de phase et la dynamique des simulations de Monte Carlo. Dans ce projet, nous prévoyons d'explorer cette connexion de manière systématique pour d'autres modèles, avec pour but de transférer l'intuition sur les transitions de phase de la physique à l'étude de la vitesse de convergence des chaînes de Markov, et vice-versa. Ces échanges pourraient avoir des conséquences importantes dans les deux domaines.
De plus des développements de techniques permettant de générer de manière aléatoire divers types d'objets combinatoires font appel aux chaînes de Markov rapidement mélangeantes. Il s'agit, dans ce cas, de partir d'un état donné du système et, par une marche aléatoire "pas trop longue" sur le graphe des états, d'arriver à un état aléatoire. Il faut donc, là aussi, que la marche corresponde à une chaîne de Markov qui "mélange rapidement".
Coupe maximum dans un graphe: De nombreux matériaux physiques désordonnés présentent des propriétés thermodynamiques inhabituelles à basse température. Dans une grande mesure, une compréhension des phases exotiques dans ce régime dépend de la connaissance de l'état de plus faible énergie. Déterminer cet état est un problème d'optimisation combinatoire, ce qui explique l'intérêt des chercheurs en physique statistique pour cette discipline. En particulier, le problème de la coupe maximum n'est autre que celui du calcul du fondamental dans le modèle d'Ising anti-ferromagnétique dans un graphe. Nous avons déjà travaillé sur le cas des graphes denses et le cas euclidien. D'une part, les algorithmes développés gagneraient à être simplifiés. D'autre part, l'analyse de la valeur dans le cas stochastique serait intéressante. Le but ici est d'obtenir une description probabiliste de l'optimum quand le volume devient grand, ou ce qui est équivalent, quand le nombre de points tend vers l'infini. Pour cela, on peut utiliser une approche purement numérique, ou une approche analytique, dérivant des approximations ou des bornes. (Les méthodes associées sont basées sur des calculs perturbatifs ou variationnels.) Une approche qui a eu beaucoup de succès est de considérer la limite de grande dimension. Dans de nombreux cas, cette limite est non triviale mais est néanmoins calculable par les approches analytiques. Notre approche combine la simulation directe (avec bien entendu des astuces numériques pour améliorer la statistique et la convergence) et le calcul analytique (basé le plus souvent sur la méthode des répliques qui donne des solutions exactes pour certains ensembles de désordre). Récemment, nous avons trouvé numériquement des lois asymptotiques pour la solution optimale dans plusieurs ensembles de désordre graphes aléatoires lacunaires pour la coupe maximum. Dans les cas que nous avons étudiés, une approximation appelée ``champ moyen'' s'est révélée très bonne quantitativement. Nous souhaitons compléter ces études en traitant d'autres ensembles : points aléatoires pour la coupe maximum. De plus, l'expérience que nous avons acquise nous encourage à développer une série de perturbations autour de la méthode champ moyen. Une retombée de cette étude sera une détermination de la nature de la singularité à grande dimension pour ces problèmes, singularité qui reste pour l'instant mystérieuse.
Problèmes d'optimisation et complexité typique: Le problème de satisfiabilité (SAT) est le problème central de la théorie de la complexité. Il est à l'origine de la classe des problèmes difficiles, dits NP-complets, qui ont des applications dans de nombreux domaines en intelligence artificielle, en recherche opérationnelle, en théorie de la décision. Les instances ``typiques'' de 3-SAT sont-elles difficiles à résoudre ? Lorsque l'on considère des instances aléatoires du problème 2-SAT ou 3-SAT, un phénomène de seuil apparaît, similaire à une transition de phase. Notre travail porte sur la détermination de bornes rigoureuses sur la valeur du seuil [12], sur la conception d'algorithmes randomisés efficaces, sur l'implantation, l'analyse et la comparaison avec d'autres heuristiques. Nous souhaitons également explorer les différences entre 3-SAT et 2-SAT au voisinage du seuil, dans l'attente que la nature de la transition de phase (partiellement abordable par la théorie des réppliques) nous aidera à mieux comprendre la différence structurelle entre les complexités des deux problèmes.
Note.
Certains des travaux des participants à la proposition sont
disponibles sur internet. Voir, par exemple: