# Statistical mechanics methods and phase transitions in optimization problems

@article{Martin2001StatisticalMM, title={Statistical mechanics methods and phase transitions in optimization problems}, author={Olivier C. Martin and R{\'e}mi Monasson and Riccardo Zecchina}, journal={Theor. Comput. Sci.}, year={2001}, volume={265}, pages={3-67} }

Recently, it has been recognized that phase transitions play an important role in the probabilistic analysis of combinatorial optimization problems. However, there are in fact many other relations that lead to close ties between computer science and statistical physics. This review aims at presenting the tools and concepts designed by physicists to deal with optimization or decision problems in a language accessible for computer scientists and mathematicians, with no prerequisites in physics… Expand

#### Figures and Topics from this paper

#### 153 Citations

Survey on computational complexity with phase transitions and extremal optimization

- Mathematics, Computer Science
- Proceedings of the 48h IEEE Conference on Decision and Control (CDC) held jointly with 2009 28th Chinese Control Conference
- 2009

This survey reviews the latest research results from fundamental to practice about the connection between computational complexity and phase transitions, and introduces the concepts, fundamentals, algorithms and applications of extremal optimization from its capability of self-organized criticality, backbone analysis and co-evolution moving to a far-from-equilibrium state. Expand

A Random Walk in Statistical Physics

- Mathematics
- 2001

This thesis deals with some aspects of the physics of disordered systems. It consists of four papers and an introductory part.
An introduction, suitable for physicists, to theoretical computer… Expand

Phase transitions and complexity in computer science : an overview of the statistical physics approach to the random satis % ability problem

- 2002

Phase transitions, ubiquitous in condensed matter physics, are encountered in computer science too. The existence of critical phenomena has deep consequences on computational complexity, that is the… Expand

Probabilistic Methods in Landscape Analysis: phase transitions, interaction structures, and complexity measures

- 2004

In recent years, the study of the phase transition behavior and typical-case complexity of search and optimization problems have become an active research topic, drawing attention from researchers… Expand

Phase transitions and complexity in computer science: an overview of the statistical physics approach to the random satisfiability problem

- Computer Science
- 2002

Concepts and methods borrowed from the statistical physics of disordered and out-of-equilibrium systems shed new light on the dynamical operation of solving algorithms. Expand

RANDOM COMBINATORIAL OPTIMIZATION PROBLEMS: MEAN FIELD AND FINITE-DIMENSIONAL RESULTS

- Physics, Mathematics
- 2018

This PhD thesis is organized as follows. In the first two chapters I will review some basic notions of statistical physics of disordered systems, such as random graph theory, the mean-field… Expand

approach to the random satisability problem

- Computer Science
- 2002

Concepts and methods borrowed from the statistical physics of disordered and out-of-equilibrium systems shed new light on the dynamical operation of solving algorithms. Expand

A statistical physics approach to different problems in network theory

- Mathematics
- 2015

Statistical physics, originally developed to describe thermodynamic systems, has been playing for the last decades a central role in modelling an incredibly large and heterogeneous set of different… Expand

Statistical Physics and Network Optimization Problems

- Computer Science
- 2015

The so called cavity method and the related message-passing algorithms (Belief Propagation and variants) which can be used to analyze and solve optimization problems over random structures. Expand

Phase transitions of the typical algorithmic complexity of the random satisfiability problem studied with linear programming

- Physics, Computer Science
- PloS one
- 2019

It is demonstrated that the technique leads to one simple-to-understand transition for the well known 2-SAT problem and that the hardness transitions are not driven by changes of any of various standard percolation or solution space properties of the problem instances. Expand

#### References

SHOWING 1-10 OF 124 REFERENCES

Comparing mean field and Euclidean matching problems

- Physics
- 1998

Abstract:Combinatorial optimization is a fertile testing ground for statistical physics methods developed in the context of disordered systems, allowing one to confront theoretical mean field… Expand

Application of statistical mechanics to NP-complete problems in combinatorial optimisation

- Mathematics
- 1986

Recently developed techniques of the statistical mechanics of random systems are applied to the graph partitioning problem. The averaged cost function is calculated and agrees well with numerical… Expand

A physicist's approach to number partitioning

- Computer Science, Mathematics
- Theor. Comput. Sci.
- 2001

It can be shown that solving a number portioning problem of size N to some extent corresponds to locating the minimum in an unsorted list of O(2N ) numbers and it is not surprising that known heuristics for the partitioning problem are not signi4cantly better than simple random search. Expand

Simplest random K-satisfiability problem

- Mathematics, Computer Science
- Physical review. E, Statistical, nonlinear, and soft matter physics
- 2001

We study a simple and exactly solvable model for the generation of random satisfiability problems. These consist of gammaN random boolean constraints which are to be satisfied simultaneously by N… Expand

Frustrated Systems: Ground State Properties via Combinatorial Optimization

- Mathematics, Physics
- 1997

An introduction to the application of combinatorial optimization methods to ground state calculations of frustrated, disordered systems is given. We discuss the interface problem in the random bond… Expand

Statistical mechanics perspective on the phase transition in vertex covering of finite-connectivity random graphs

- Computer Science, Mathematics
- Theor. Comput. Sci.
- 2001

The vertex-cover problem is studied for random graphs GN,cN having N vertices and cN edges and a transition in the coverability at a c-dependent threshold x =xc(c) appears, where xN is the cardinality of the vertex cover. Expand

Statistical Mechanics of the K--Satisfiability Model

- Physics, Mathematics
- 1996

The Random K-Satisfiability Problem, consisting in verifying the existence of an assignment of N Boolean variables that satisfy a set of M=alpha N random logical clauses containing K variables each,… Expand

Phase coexistence and finite size scaling in random combinatorial problems

- Mathematics, Physics
- 2001

We study an exactly solvable version of the well known random Boolean satisfiability (SAT) problem, the so-called random XOR-SAT problem. Rare events are shown to affect the combinatorial `phase… Expand

Determining computational complexity from characteristic ‘phase transitions’

- Computer Science
- Nature
- 1999

An analytic solution and experimental investigation of the phase transition in K -satisfiability, an archetypal NP-complete problem, is reported and the nature of these transitions may explain the differing computational costs, and suggests directions for improving the efficiency of search algorithms. Expand

Phase Transitions and the Search Problem

- Mathematics, Computer Science
- Artif. Intell.
- 1996

Techniques that were originally developed in statistical mechanics can be applied to search problems that arise commonly in artificial intelligence and predict that abrupt changes in computational cost should occur universally, as heuristic effectiveness or search space topology is varied. Expand