Note to users. If you're seeing this message, it means that your browser cannot find this page's style/presentation instructions -- or possibly that you are using a browser that does not support current Web standards. Find out more about why this message is appearing, and what you can do to make your experience of our site the best it can be.
Analytic and Algorithmic Solution of Random Satisfiability Problems
M. Mézard,1G. Parisi,12R. Zecchina13*
We study the satisfiability of random Boolean expressions built
from many clauses with K variables per clause
(K-satisfiability).Expressions with a ratio of clauses to
variables less than athreshold c are almost
always satisfiable, whereas thosewith a ratio above this threshold are
almost always unsatisfiable.We show the existence of an intermediate
phase below c,where the proliferation of
metastable states is responsible forthe onset of complexity in search
algorithms. We introduce a classof optimization algorithms that can
deal with these metastablestates; one such algorithm has been tested
successfully on thelargest existing benchmark of K-satisfiability.
1 Laboratoire de Physique Théorique et
Modèles Statistiques, CNRS and Université Paris Sud,
Bât. 100, 91405 Orsay Cedex, France.
2 Sezione
INFN, SMC and UdRm1 of INFM, Università "La Sapienza," P.le
A. Moro 2, 00185 Roma, Italy.
3 Abdus Salam
International Centre for Theoretical Physics, Str. Costiera 11, 34100 Trieste, Italy.
*
To whom correspondence should be addressed. E-mail:
zecchina{at}ictp.trieste.it
of clauses to
variables less than a threshold 
