Clustering of solutions in the random satisfiability problem

M. Mezard, T. Mora, R. Zecchina

Using elementary rigorous methods we prove the existence of a clustered phase in the random $K$-SAT problem, for $K\ge 8$. In this phase the solutions are grouped into clusters wh…