摘要翻译：
本文介绍了两种用于量化布尔公式(QBF)的消息传递算法。第一类是基于消息传递的启发式，它可以通过分配通用变量来证明QBF的不可满足性，这样剩余的公式是不可满足的。在第二类中，我们使用消息传递来指导Davis-Putnam Logemann-Loveland(DPLL)完全求解器的分支启发式。数值实验表明，在随机QBFs上，我们的分支启发式算法相对于现有的求解器具有鲁棒的指数效率增益。我们还设法从QBFLIB库中解决了一些以前未解决的基准测试。除此之外，我们的研究为在小型系统中使用消息传递以及在完整的求解器中使用子程序提供了帮助。
---
英文标题：
《Message passing for quantified Boolean formulas》
---
作者：
Pan Zhang, Abolfazl Ramezanpour, Lenka Zdeborov\'a and Riccardo
  Zecchina
---
最新提交年份：
2012
---
分类信息：

一级分类：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中的材料。
--
一级分类：Physics        物理学
二级分类：Disordered Systems and Neural Networks        无序系统与神经网络
分类描述：Glasses and spin glasses; properties of random, aperiodic and quasiperiodic systems; transport in disordered media; localization; phenomena mediated by defects and disorder; neural networks
眼镜和旋转眼镜；随机、非周期和准周期系统的性质；无序介质中的传输；本地化；由缺陷和无序介导的现象；神经网络
--

---
英文摘要：
  We introduce two types of message passing algorithms for quantified Boolean formulas (QBF). The first type is a message passing based heuristics that can prove unsatisfiability of the QBF by assigning the universal variables in such a way that the remaining formula is unsatisfiable. In the second type, we use message passing to guide branching heuristics of a Davis-Putnam Logemann-Loveland (DPLL) complete solver. Numerical experiments show that on random QBFs our branching heuristics gives robust exponential efficiency gain with respect to the state-of-art solvers. We also manage to solve some previously unsolved benchmarks from the QBFLIB library. Apart from this our study sheds light on using message passing in small systems and as subroutines in complete solvers.
---
PDF链接：
https://arxiv.org/pdf/1202.2536