...
  • 主题
高级搜索  >
历史搜索 清空历史
首页> 外文期刊>The European physical journal, B. Condensed matter physics >Statistical physics analysis of the computational complexity of solving random satisfiability problems using backtrack algorithms
【24h】

Statistical physics analysis of the computational complexity of solving random satisfiability problems using backtrack algorithms

机译：使用回溯算法解决随机可满足性问题的计算复杂度的统计物理分析

获取原文
获取原文并翻译 | 示例
           
页面导航
  • 摘要
  • 著录项
  • 相似文献
  • 相关主题

摘要

The computational complexity of solving random 3-Satisfiability (3-SAT) problems is investigated using statistical physics concepts and techniques related to phase transitions, growth processes and (real-space) renormalization flows. 3-SAT is a representative example of hard computational tasks; it consists in knowing whether a set of αN randomly drawn logical constraints involving N Boolean variables can be satisfied altogether or not. Widely used solving procedures, as the Davis-Putnam-Loveland-Logemann (DPLL) algorithm, perform a systematic search for a solution, through a sequence of trials and errors represented by a search tree. The size of the search tree accounts for the computational complexity, i.e. the amount of computational efforts, required to achieve resolution. In the present study, we identify, using theory and numerical experiments, easy (size of the search tree scaling polynomially with N) and hard (exponential scaling) regimes as a function of the ratio α of constraints per variable. The typical complexity is explicitly calculated in the different regimes, in very good agreement with numerical simulations. Our theoretical approach is based on the analysis of the growth of the branches in the search tree under the operation of DPLL. On each branch, the initial 3-SAT problem is dynamically turned into a more generic 2+p-SAT problem, where p and 1 - p are the fractions of constraints involving three and two variables respectively. The growth of each branch is monitored by the dynamical evolution of α and p and is represented by a trajectory in the static phase diagram of the random 2+p-SAT problem. Depending on whether or not the trajectories cross the boundary between satisfiable and unsatisfiable phases, single branches or full trees are generated by DPLL, resulting in easy or hard resolutions. Our picture for the origin of complexity can be applied to other computational problems solved by branch and bound algorithms.
机译：使用统计物理概念和与相变，增长过程和（实空间）重归一化流有关的技术，研究了解决随机3-满足性（3-SAT）问题的计算复杂性。 3-SAT是硬计算任务的代表示例;它在于知道是否可以完全满足一组涉及N个布尔变量的αN个随机绘制的逻辑约束。广泛使用的求解程序，例如Davis-Putnam-Loveland-Logemann（DPLL）算法，通过搜索树代表的一系列试验和错误来对系统进行搜索。搜索树的大小说明了实现分辨率所需的计算复杂性，即计算工作量。在本研究中，我们使用理论和数值实验，根据每个变量的约束比率α来确定简单（搜索树的大小按N多项式缩放）和硬（指数缩放）方案。典型的复杂度是在不同的情况下显式计算的，与数值模拟非常吻合。我们的理论方法是基于DPLL操作下搜索树中分支增长的分析。在每个分支上，最初的3-SAT问题都会动态地转化为更通用的2 + p-SAT问题，其中p和1-p是分别涉及三个和两个变量的约束分数。每个分支的增长通过α和p的动态演变来监控，并在2 + p-SAT随机问题的静态相位图中以轨迹表示。根据轨迹是否跨越可满足和不可满足的相位之间的边界，DPLL会生成单个分支或完整树，从而产生简单或硬性的分辨率。我们对于复杂性起源的描述可以应用于分支定界算法解决的其他计算问题。

著录项

相似文献

  • 外文文献
  • 中文文献
  • 专利
获取原文

客服邮箱：kefu@zhangqiaokeyan.com

京公网安备：11010802029741号 ICP备案号：京ICP备15016152号-6 六维联合信息科技 (北京) 有限公司©版权所有

  • 客服微信

  • 服务号