Archivio Istituzionale della RicercaUsing elementary rigorous methods we prove the existence of a clustered phase in the random K-SAT problem, for K >= 8. In this phase the solutions are grouped into clusters which are far away from each other. The results are in agreement with previous predictions of the cavity method and give a rigorous confirmation to one of its main building blocks. It can be generalized to other systems of both physical and computational interest.
Clustering of solutions in the random satisfiability problem / Mezard, M; Mora, T; Zecchina, Riccardo. - In: PHYSICAL REVIEW LETTERS. - ISSN 0031-9007. - 94:(2005), p. 197205. [10.1103/PhysRevLett.94.197205]
Clustering of solutions in the random satisfiability problem
ZECCHINA, RICCARDO
2005
Abstract
Using elementary rigorous methods we prove the existence of a clustered phase in the random K-SAT problem, for K >= 8. In this phase the solutions are grouped into clusters which are far away from each other. The results are in agreement with previous predictions of the cavity method and give a rigorous confirmation to one of its main building blocks. It can be generalized to other systems of both physical and computational interest.
Pubblicazioni consigliate
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
https://hdl.handle.net/11583/1829428
Attenzione
Attenzione! I dati visualizzati non sono stati sottoposti a validazione da parte dell'ateneo