  The aim of this review paper is to give a panoramic of the impact of spin
glass theory and statistical physics in the study of the K-sat problem. The
introduction of spin glass theory in the study of the random K-sat problem has
indeed left a mark on the field, leading to some groundbreaking descriptions of
the geometry of its solution space, and helping to shed light on why it seems
to be so hard to solve.
  Most of the geometrical intuitions have their roots in the
Sherrington-Kirkpatrick model of spin glass. We'll start Chapter 2 by
introducing the model from a mathematical perspective, presenting a selection
of rigorous results and giving a first intuition about the cavity method. We'll
then switch to a physical perspective, to explore concepts like pure states,
hierarchical clustering and replica symmetry breaking.
  Chapter 3 will be devoted to the spin glass formulation of K-sat, while the
most important phase transitions of K-sat (clustering, condensation, freezing
and SAT/UNSAT) will be extensively discussed in Chapter 4, with respect their
complexity, free-entropy density and the Parisi 1RSB parameter.
  The concept of algorithmic barrier will be presented in Chapter 5 and
exemplified in detail on the Belief Propagation (BP) algorithm. The BP
algorithm will be introduced and motivated, and numerical analysis of a
BP-guided decimation algorithm will be used to show the role of the clustering,
condensation and freezing phase transitions in creating an algorithmic barrier
for BP.
  Taking from the failure of BP in the clustered and condensed phases, Chapter
6 will finally introduce the Cavity Method to deal with the shattering of the
solution space, and present its application to the development of the Survey
Propagation algorithm.
