Statistical Mechanics of the Random K-Sat Model

Abstract

The Random K-Satisfiability Problem, consisting in verifying the existence of an assignment of $N$ Boolean variables that satisfy a set of $M=\alpha N$ random logical clauses containing $K$ variables each, is studied using the replica symmetric framework of disordered systems. The detailed structure of the analytical solution is discussed for the different cases of interest $K=2$, $K\ge 3$ and $K\gg 1$. We present an iterative scheme allowing to obtain exact and systematically improved solutions for the replica symmetric functional order parameter. The caculation of the number of solutions, which allowed us [Phys. Rev. Lett. 76, 3881 (1996)] to predict a first order jump at the threshold where the Boolean expressions become unsatisfiable with probability one, is thoroughly displayed. In the case $K=2$, the (rigourously known) critical value ($=1$) of the number of clauses per Boolean variable is recovered while for $K\ge 3$ we show that the system exhibits a replica symmetry breaking transition. The annealed approximation is proven to be exact for large $K$.