approach to the random satisability problem
Giulio Biroli, Simona Maria Cocco · 2002
Phase transitions, ubiquitous in condensed matter physics, are encountered in computer science 13 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 15 borrowed from the statistical physics of disordered and out-of-equilibrium systems shed new light on the dynamical operation of solving algorithms. c � 2002 Published by Elsevier 17 Science B.V. PACS: ; ; 19