Clustering at the Phase Transition
Clustering at the Phase Transition
复制标题
DOI：
--
复制
发表时间：
1997-07
期刊：
影响因子：
--
通讯作者：
A. Parkes
中科院分区：
文献类型：
--
作者：
A. Parkes
许多问题集成表现出相变，这与解决问题实例的平均成本中的大峰值相关联。然而，这个峰值并不一定是由于缺乏解决方案：实际上，解决方案的平均数量通常是指数级的。在这里，我们研究这种情况下，在随机3SAT的可满足性过渡的背景下。我们发现，一个显着的子类的实例出现，因为我们跨越相变。这些实例的特征在于，它们的变量中约有85-95%出现在一元素数蕴涵（UPI）中，其余变量受到很少的约束。在这种情况下，模型不是随机分布的，而是都位于一个指数级大的集群中，但仍然允许简单的描述。研究UPI对局部搜索算法WSAT的影响表明，这些“单簇”实例更难解决，我们将它们在相变时的出现与搜索成本的峰值联系起来。
Many problem ensembles exhibit a phase transition that is associated with a large peak in the average cost of solving the problem instances. However, this peak is not necessarily due to a lack of solutions: indeed the average number of solutions is typically exponentially large. Here, we study this situation within the context of the satisfiability transition in Random 3SAT. We find that a significant subclass of instances emerges as we cross the phase transition. These instances are characterized by having about 85-95% of their variables occurring in unary prime implicates (UPIs), with their remaining variables being subject to few constraints. In such instances the models are not randomly distributed but all lie in a cluster that is exponentially large, but still admits a simple description. Studying the effect of UPIs on the local search algorithm WSAT shows that these "single-cluster" instances are harder to solve, and we relate their appearance at the phase transition to the peak in search cost.