A variational description of the ground state structure in random satisfiability problems

A variational approach to finite connectivity spin-glass-like models is dev eloped and applied to describe the structure of optimal solutions in random satisfiability problems. Our variational scheme accurately reproduces the known replica symmetric results and also allows for the inclusion of replic a symmetry breaking effects. For the 3-SAT problem, we find two transitions as the ratio alpha of logical clauses per Boolean variables increases. At the first one alpha(s) similar or equal to 3.96, a non-trivial organization of the solution space in geometrically separated clusters emerges. The mul tiplicity of these clusters as well as the typical distances between differ ent solutions are calculated. At the second threshold alpha(c) similar or e qual to 4.48, satisfying assignments disappear and a finite fraction B-o si milar or equal to 0.13 of variables are overconstrained and take the same v alues in all optimal (though unsatisfying) assignments. These values have t o be compared to alpha(c) similar or equal to 4.27, B-o similar or equal to 0.4 obtained from numerical experiments on small instances. Within the pre sent variational approach, the SAT-UNSAT transition naturally appears as a mixture of a first and a second order transition. For the mixed 2 + p-SAT w ith p < 2/5, the behavior is as: expected much simpler: a unique smooth tra nsition from SAT to UNSAT takes place at alpha(c) = 1/(1 - p).