Numéro |
J. Physique Lett.
Volume 46, Numéro 17, septembre 1985
|
|
---|---|---|
Page(s) | 763 - 770 | |
DOI | https://doi.org/10.1051/jphyslet:019850046017076300 |
DOI: 10.1051/jphyslet:019850046017076300
Mean-field theory for optimization problems
H. OrlandService de Physique Théorique, CEN Saclay, 91191 Gif-sur-Yvette Cedex, France
Abstract
A mean-field theory for optimization problems of the Travelling Salesman type, or of the Matching type, is presented. It involves an infinite set of order parameters which measure the lack of self-averageness of the system and its degree of freezing. We further conjecture that NP-completeness is associated with replica symmetry breaking.
Résumé
On présente une théorie de champ moyen pour les problèmes d'optimisation du type « Voyageur de Commerce » ou problèmes d'« Appariement ». Cette théorie de champ moyen s'exprime à l'aide d'un ensemble infini de paramètres d'ordre, qui mesurent l'absence d'auto-moyennage du système et donc son degré de gel. On conjecture que la NP-complexité est associée à la brisure de symétrie des répliques.
0520 - Statistical mechanics.
Key words
statistical mechanics -- travelling salesman problems -- matching problems -- partition function -- mean field theory -- optimization problems -- order parameters -- self averageness -- freezing -- NP completeness -- replica symmetry breaking