发帖
雷达卡
摘要翻译：
研究了随机图中双色问题解的熵景观，这是一个具有代表性的困难约束满足问题。我们的目标是对不同算法处理的解簇类型进行分类。在研究的第一部分中，我们使用腔方法获得了具有给定内部熵的团簇数目，并确定了问题的相图，如动力学、刚性和SAT-UNSAT跃迁。在论文的第二部分，我们分析了不同的算法，并在问题的熵景观中定位它们的行为。例如，我们证明了基于信念传播的抽取策略的平滑版本能够找到属于次优势团簇的解，甚至超过所谓的刚性转变，即热力学相关的团簇变得冻结。这些非平衡解属于最可能的未冻结团簇。
---
英文标题：
《Entropy landscape and non-Gibbs solutions in constraint satisfaction
problems》
---
作者：
L. Dall'Asta, A. Ramezanpour and R. Zecchina
---
最新提交年份：
2008
---
分类信息：
一级分类：Physics 物理学
二级分类：Statistical Mechanics 统计力学
分类描述：Phase transitions, thermodynamics, field theory, non-equilibrium phenomena, renormalization group and scaling, integrable models, turbulence
相变，热力学，场论，非平衡现象，重整化群和标度，可积模型，湍流
--
一级分类：Computer Science 计算机科学
二级分类：Computational Complexity 计算复杂度
分类描述：Covers models of computation, complexity classes, structural complexity, complexity tradeoffs, upper and lower bounds. Roughly includes material in ACM Subject Classes F.1 (computation by abstract devices), F.2.3 (tradeoffs among complexity measures), and F.4.3 (formal languages), although some material in formal languages may be more appropriate for Logic in Computer Science. Some material in F.2.1 and F.2.2, may also be appropriate here, but is more likely to have Data Structures and Algorithms as the primary subject area.
涵盖计算模型，复杂度类别，结构复杂度，复杂度折衷，上限和下限。大致包括ACM学科类F.1（抽象设备的计算）、F.2.3（复杂性度量之间的权衡）和F.4.3（形式语言）中的材料，尽管形式语言中的一些材料可能更适合于计算机科学中的逻辑。在F.2.1和F.2.2中的一些材料可能也适用于这里，但更有可能以数据结构和算法作为主要主题领域。
--
---
英文摘要：
We study the entropy landscape of solutions for the bicoloring problem in random graphs, a representative difficult constraint satisfaction problem. Our goal is to classify which type of clusters of solutions are addressed by different algorithms. In the first part of the study we use the cavity method to obtain the number of clusters with a given internal entropy and determine the phase diagram of the problem, e.g. dynamical, rigidity and SAT-UNSAT transitions. In the second part of the paper we analyze different algorithms and locate their behavior in the entropy landscape of the problem. For instance we show that a smoothed version of a decimation strategy based on Belief Propagation is able to find solutions belonging to sub-dominant clusters even beyond the so called rigidity transition where the thermodynamically relevant clusters become frozen. These non-equilibrium solutions belong to the most probable unfrozen clusters.
---
PDF链接：
https://arxiv.org/pdf/801.289
京公网安备 11010802022788号
