acta physica slovaca |
|
|
Acta Physica Slovaca 59, No.3, 169-303 (2009) (88 pages)
Statistical physics of hard optimization problems Lenka Zdeborová Theoretical Division and Center for Nonlinear Studies, Los Alamos National Laboratory, NM 87545 USA Full text: ::pdf :: (Received 26 May 2009, accepted 3 June 2009) Abstract: Optimization is fundamental in many areas of science, from computer science and information theory to engineering and statistical physics, as well as to biology or social sciences. It typically involves a large number of variables and a cost function depending on these variables. Optimization problems in the non-deterministic polynomial (NP)-complete class are particularly difficult, it is believed that the number of operations required to minimize the cost function is in the most difficult cases exponential in the system size. However, even in an NP-complete problem the practically arising instances might, in fact, be easy to solve. The principal question we address in this article is: How to recognize if an NP-complete constraint satisfaction problem is typically hard and what are the main reasons for this? We adopt approaches from the statistical physics of disordered systems, in particular the cavity method developed originally to describe glassy systems. We describe new properties of the space of solutions in two of the most studied constraint satisfaction problems - random satisfiability and random graph coloring. We suggest a relation between the existence of the so-called frozen variables and the algorithmic hardness of a problem. Based on these insights, we introduce a new class of problems which we named ”locked” constraint satisfaction, where the statistical description is easily solvable, but from the algorithmic point of view they are even more challenging than the canonical satisfiability. PACS: 89.70.Eg, 75.10.Nr, 64.70.qd, 02.10.Ox, 89.20.Ff Keywords: Constraint satisfaction problems, Random graphs coloring problem, Average computational complexity, Cavity method, Spin glasses, Replica symmetry breaking, Clustering of solutions, Belief propaga- tion, Satisfiability threshold, Reconstruction on trees |
ISSN 1336-040X (online) ISSN 0323-0465 (printed) For authors: ActaStyle.cls |
| © published by Institute of Physics, Slovak Academy of Sciences. All rights reserved. | |