Gibbs states and the set of solutions of random constraint satisfaction problems
Gibbs states and the set of solutions of random constraint satisfaction problems
复制标题
DOI：
10.1073/pnas.0703685104
复制
发表时间：
2007-06-19
影响因子：
11.1
通讯作者：
Zdeborova, Lenka
中科院分区：
文献类型：
--
作者：
Krzakala, Florent;Montanari, Andrea;Zdeborova, Lenka
随机约束满足问题的一个实例定义了一个大积空间chi(N)（赋值集）的随机子集S（解集）。我们考虑了两个典型的问题集合（随机正则图的随机k-可满足性和q-着色性），并研究了s支持下的均匀测度。随着每个变量的约束数量的增加，该测度首先分解成指数数量的纯态（“簇”），随后凝聚在最大的这种状态上。在凝点以上，n个最大的态所携带的质量遵循泊松-狄利克雷过程。对于典型的大型实例，这两个转换非常明显。我们确定他们的精确位置。此外，我们根据问题中不同变量之间的不同相关性概念提供了每个相变的正式定义。相关程度自然会影响许多搜索/采样算法的性能。经验证据表明，局部蒙特卡罗马尔可夫链策略在聚类相变之前是有效的，在信念传播到凝聚点之前是有效的。最后，精细化的消息传递技术（如调查传播）也可能超过这个阈值。
An instance of a random constraint satisfaction problem defines a random subset S (the set of solutions) of a large product space chi(N) (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.