Statistical mechanics of the random [Formula Presented]-satisfiability model

The random [Formula Presented]-satisfiability problem, consisting in verifying the existence of an assignment of [Formula Presented] Boolean variables that satisfy a set of [Formula Presented] random logical clauses containing [Formula Presented] variables each, is studied using the replica symmetric framework of diluted disordered systems. We present an exact iterative scheme for the replica symmetric functional order parameter together for the different cases of interest [Formula Presented], [Formula Presented], and [Formula Presented]. The calculation 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 [Formula Presented], the (rigorously known) critical value [Formula Presented] of the number of clauses per Boolean variable is recovered while for [Formula Presented] we show that the system exhibits a replica symmetry breaking transition. The annealed approximation is proven to be exact for large [Formula Presented].