Recently, it has been recognized that phase transitions
play an important role in the probabilistic analysis of
combinatorial optimization problems. This lecture aims at
presenting the tools and concepts designed by physicists
to deal with optimization or decision problems in an accessible
language for computer scientists and mathematicians, with no
prerequisites in physics. I shall focus here on the transitions
taking place in the covering of random graphs and the
satisfaction of random Boolean formulas, and their relationship
with resolution complexity.
Copyright. All Rights Reserved.