Nov, 2014

关于大 k 可满足性猜想的证明

PDF
TL;DR我们利用统计物理学中的一步副本对称性预测，为所有的 k≥k_0，建立了随机 k-SAT 的可满足性阈值，给出满足阈值和不满足阈值的限制密度的显式计算公式，并用一种新的分析方法对随机图进行矩计算，将一个高维的优化问题映射到了一个更易处理的分析树递归问题，证明了我们的阈值计算方法适用于 1-RSB 普适性类中的各种随机约束满足问题。
satisfiability thresholdk-satdensityanalytic method1-rsb universality class
发现论文，激发创造
  • 低次多项式随机 $k$- 可满足性问题的算法相变

    研究了在 $k$-SAT 问题中寻找满足分配的算法任务，证明了低次数多项式算法类无法在特定子密度下解决该问题，这是关于任何算法类在与 Fix 相等水平难度下的首个困难结果。

    Jun, 2021

  • 随机约束满足问题的解空间几何

    该论文研究了随机约束满足问题的解空间结构，并证明了在解消失之前，它们会组成指数数量的簇，并且每个簇都相对较小且相距较远。此外，每个簇内的大部分变量都被冻结，并提出 Survey Propagation 算法的一项重要假设。

    Nov, 2006

  • 相变引起的算法障碍

    研究随机 CSP 问题和多项式时间算法无法寻找解决方案的相位转变，并运用一般技术准确地证明 $k$- 着色的相位转变推出所有已知多项式时间算法的失败点。

    Mar, 2008

  • 随机可满足性问题中的种植解的复杂性

    本文提出和研究了一种插入 k-SAT 模型，描述了一个插入分配 σ 和一个具有 k 个文字的子句分布的实例，对于分布复杂性的倒数关联了查询算法的统计下界。该证明引入了一种新的分析统计查询算法的通用技术，并指出了所有种植任务空间中的几何剪枝现象。

    Nov, 2013

  • Survey propagation: 一种可满足性问题的算法

    本研究介绍了一种新的消息传递算法，可有效找到困难区域内变量的满足性分配，并应用于随机生成的具有一定数量的变量、布尔运算和公式的问题中，问题的困难程度与解决思路中 “聚类” 现象相关

    Dec, 2002

  • 布尔可满足性问题的抽样技术

    提出使用有限独立哈希的新方法来解决 boolean satisfiability 问题，并基于此方法设计了两个实用算法：一个近似均匀生成器和一个可扩展的近似模型计数器，该方法具有强大的理论保证和可扩展性，可适用于不同的应用领域。

    Apr, 2014

  • 生成难解布尔可满足问题的简易模型

    本文利用 RB 和 RD 模型展示随机 CSP 实例的理论和实际兴趣，证明在限制域大小和约束紧密性的情况下，可以保证渐近相变阈值点的准确定位，并且所有实例在阈值处的困难度保证是指数级别的。

    Sep, 2005

  • 非布尔矩阵的 Ihara-Bass 公式及随机 CSP 的强证明

    对称矩阵的 “非返环” 矩阵的定义和 “Ihara-Bass” 类型公式的证明，用于证明具有 k 个变量的约束满足问题（k-CSP）的多项式时间强驳斥结果，同时提出了新的结果。

    Apr, 2022

  • Gibbs 状态与随机约束满足问题的解集

    研究了随机约束满足性问题的两个典型集合，并主要考虑其相空间的纯态、相变等问题，阐述了相变精确位置和多种算法在不同相的表现，包括局部蒙特卡罗马尔科夫链、置信传播和调查传播技术。

    Dec, 2006

  • CSP 的次指数近似算法：从密集到几乎稀疏

    本文从大规模消耗能源问题出发，对 mAP 米级别的近似精度提出解决方案，同时研究了深度的语义信息和有限的上下文信息如何影响计算性能。

    Jul, 2015