Abstract
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 resolution times of various optimization or decision problems. 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.
| Original language | English |
|---|---|
| Pages (from-to) | 381-394 |
| Number of pages | 14 |
| Journal | Physica A: Statistical Mechanics and its Applications |
| Volume | 306 |
| DOIs | |
| Publication status | Published - 1 Apr 2002 |
| Externally published | Yes |
| Event | 21th IUPAP Conference on Invited Papares (STATPHYS 21) - Cancun, Mexico Duration: 15 Jul 2001 → 21 Jul 2001 |
Keywords
- Analysis of algorithm
- Optimization
- Phase transitions
- Satisfiability
- Statistical physics