Krzakała Florent, Montanari Andrea, Ricci-Tersenghi Federico, Semerjian Guilhem, Zdeborová Lenka
Laboratoire de Physico-Chimie Théorique, Ecole Supérieure de Physique et de Chimie Industrielles, 75005 Paris, France.
Proc Natl Acad Sci U S A. 2007 Jun 19;104(25):10318-23. doi: 10.1073/pnas.0703685104. Epub 2007 Jun 13.
An instance of a random constraint satisfaction problem defines a random subset (the set of solutions) of a large product space chiN (the set of assignments). We consider two prototypical problem ensembles (random k-satisfiability and q-coloring of random regular graphs) and study the uniform measure with support on S. As the number of constraints per variable increases, this measure first decomposes into an exponential number of pure states ("clusters") and subsequently condensates over the largest such states. Above the condensation point, the mass carried by the n largest states follows a Poisson-Dirichlet process. For typical large instances, the two transitions are sharp. We determine their precise location. Further, we provide a formal definition of each phase transition in terms of different notions of correlation between distinct variables in the problem. The degree of correlation naturally affects the performances of many search/sampling algorithms. Empirical evidence suggests that local Monte Carlo Markov chain strategies are effective up to the clustering phase transition and belief propagation up to the condensation point. Finally, refined message passing techniques (such as survey propagation) may also beat this threshold.
随机约束满足问题的一个实例定义了一个大乘积空间χᴺ（赋值集）的随机子集（解集）。我们考虑两个典型的问题集（随机k可满足性和随机正则图的q着色），并研究在S上有支撑的均匀测度。随着每个变量的约束数量增加，该测度首先分解为指数数量的纯态（“簇”），随后在最大的此类状态上凝聚。在凝聚点之上，n个最大状态所承载的质量遵循泊松 - 狄利克雷过程。对于典型的大实例，这两个转变是尖锐的。我们确定它们的确切位置。此外，我们根据问题中不同变量之间相关性的不同概念，给出了每个相变的形式化定义。相关程度自然会影响许多搜索/采样算法的性能。经验证据表明，局部蒙特卡罗马尔可夫链策略在聚类相变之前是有效的，而信念传播在凝聚点之前是有效的。最后，精细的消息传递技术（如调查传播）也可能突破这个阈值。
