Clustering of solutions in the random satisfiability problem -: art. no. 197205

被引：107

作者：

Mézard, M

Mora, T

Zecchina, R

机构：

[1] Univ Paris 11, Lab Phys Theor & Modeles Stat, F-91405 Orsay, France

[2] Abdus Salam Int Ctr Theoret Phys, I-34100 Trieste, Italy

来源：

PHYSICAL REVIEW LETTERS | 2005年 / 94卷 / 19期

关键词：

D O I：

10.1103/PhysRevLett.94.197205

中图分类号：

O4 [物理学];

学科分类号：

0702 ;

摘要：

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.

引用

页数：4

共 31 条

[1] The threshold for random k-SAT is 2k log 2-O(k) [J].