Clustering of solutions in the random satisfiability problem
Clustering of solutions in the random satisfiability problem
复制标题
DOI：
10.1103/physrevlett.94.197205
复制
发表时间：
2005-04
影响因子：
8.6
通讯作者：
M. Mézard;Thierry Mora;R. Zecchina
中科院分区：
文献类型：
--
作者：
M. Mézard;Thierry Mora;R. Zecchina
本文用初等严格方法证明了随机K-SAT问题中的聚集相的存在性，其中K >或= 8。在这个阶段中，解决方案被分组到彼此远离的集群中。结果与以前的空腔方法的预测是一致的，并给出了严格的确认，其主要组成部分之一。它可以推广到其他系统的物理和计算的兴趣。
Using elementary rigorous methods we prove the existence of a clustered phase in the random K-SAT problem, for K > or = 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.