摘要翻译：
局部搜索算法WSat是解决可满足性(SAT)问题最成功的算法之一。该算法在求解接近所谓的“可满足性阈值”的硬随机3-SAT实例时非常有效，但在阈值附近仍然存在搜索代价的峰值，并且不同实例的代价有很大的差异。我们使用最近引入的SAT实例主干的概念，对WSat在高代价随机实例上的分析做出了许多重要贡献。主干是一个实例所包含的一组文字。我们发现，解的个数对于小主干的情况可以很好地预测成本，但对于出现在阈值附近并在过约束区域占主导地位的大主干的情况，其相关性要小得多。在WSAT的早期搜索中，我们发现搜索代价与到最近解的汉明距离之间有很强的相关性。这个模式使我们引入了一个实例的主干脆弱性度量，它指示当子句被移除时主干的持久性。我们提出，用于局部搜索的高代价随机实例是那些具有非常大的主干的实例，这些主干也是脆弱的。我们认为，超过可满足性阈值的成本衰减是由于骨干网鲁棒性（与骨干网脆弱性相反）的增加。我们的假设做出了三个正确的预测。首先，在控制其他因素的情况下，实例的骨干鲁棒性与局部搜索代价呈负相关。其次，最小骨干网实例（即3-SAT实例，为了使骨干网更加脆弱而被修改）对于WSAT来说异常困难。第三，在搜索过程中最常不满足的子句是那些删除对主干影响最大的子句。在了解局部搜索方法的病态性时，我们希望有助于开发新的更好的技术。
---
英文标题：
《Backbone Fragility and the Local Search Cost Peak》
---
作者：
I. P. Gent, J. Singer, A. Smaill
---
最新提交年份：
2011
---
分类信息：

一级分类：Computer Science        计算机科学
二级分类：Artificial Intelligence        人工智能
分类描述：Covers all areas of AI except Vision, Robotics, Machine Learning, Multiagent Systems, and Computation and Language (Natural Language Processing), which have separate subject areas. In particular, includes Expert Systems, Theorem Proving (although this may overlap with Logic in Computer Science), Knowledge Representation, Planning, and Uncertainty in AI. Roughly includes material in ACM Subject Classes I.2.0, I.2.1, I.2.3, I.2.4, I.2.8, and I.2.11.
涵盖了人工智能的所有领域，除了视觉、机器人、机器学习、多智能体系统以及计算和语言（自然语言处理），这些领域有独立的学科领域。特别地，包括专家系统，定理证明（尽管这可能与计算机科学中的逻辑重叠），知识表示，规划，和人工智能中的不确定性。大致包括ACM学科类I.2.0、I.2.1、I.2.3、I.2.4、I.2.8和I.2.11中的材料。
--

---
英文摘要：
  The local search algorithm WSat is one of the most successful algorithms for solving the satisfiability (SAT) problem. It is notably effective at solving hard Random 3-SAT instances near the so-called `satisfiability threshold', but still shows a peak in search cost near the threshold and large variations in cost over different instances. We make a number of significant contributions to the analysis of WSat on high-cost random instances, using the recently-introduced concept of the backbone of a SAT instance. The backbone is the set of literals which are entailed by an instance. We find that the number of solutions predicts the cost well for small-backbone instances but is much less relevant for the large-backbone instances which appear near the threshold and dominate in the overconstrained region. We show a very strong correlation between search cost and the Hamming distance to the nearest solution early in WSat's search. This pattern leads us to introduce a measure of the backbone fragility of an instance, which indicates how persistent the backbone is as clauses are removed. We propose that high-cost random instances for local search are those with very large backbones which are also backbone-fragile. We suggest that the decay in cost beyond the satisfiability threshold is due to increasing backbone robustness (the opposite of backbone fragility). Our hypothesis makes three correct predictions. First, that the backbone robustness of an instance is negatively correlated with the local search cost when other factors are controlled for. Second, that backbone-minimal instances (which are 3-SAT instances altered so as to be more backbone-fragile) are unusually hard for WSat. Third, that the clauses most often unsatisfied during search are those whose deletion has the most effect on the backbone. In understanding the pathologies of local search methods, we hope to contribute to the development of new and better techniques.
---
PDF链接：
https://arxiv.org/pdf/1106.0240