我们利用统计物理学中的一步副本对称性预测，为所有的 k≥k_0，建立了随机 k-SAT 的可满足性阈值，给出满足阈值和不满足阈值的限制密度的显式计算公式，并用一种新的分析方法对随机图进行矩计算，将一个高维的优化问题映射到了一个更易处理的分析树递归问题，证明了我们的阈值计算方法适用于 1-RSB 普适性类中的各种随机约束满足问题。

Nov, 2014

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

Dec, 2002

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

Nov, 2013

提出了一个精确算法，决定在时间复杂度 O (m)+2^{O (k^2)} 内，对于每个固定的 r≥2，是否存在一个满足至少 ((2^r-1) m+k)/2^r 个子句的布尔表达式，从而解决 Mahajan 等人未解决的开放问题。该算法基于一个在多项式时间内缩小问题规模的数据约减过程，并介绍了一种新的从参数化问题到另一个参数化问题的生物核化方法，并将其应用于证明所提出的问题具有多项式大小的内核。同时，将定参数可跟踪性和多项式大小内核的结果推广到更广泛的布尔约束满足问题。

Jul, 2009

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

Nov, 2006

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

Mar, 2008

本文首次研究了随机 $k$-CNF-XOR 公式的可满足性，并证明了 $k$-CNF-XOR 公式以及 $k = 2$ 时的相变存在性，发现了服从 $k$-CNF 和 XOR 约束之间线性权衡的惊人相变现象，并且提供了 SAT 求解器在此相变中的性能实证结果。

Feb, 2017

本文探讨了在随机 k-SAT 模型下，随着变量与子句的比例 r 的增加，满足问题的可满足性呈现相变现象，并在阈值点出现真值分配的突变，从而使得满足真值分配的相似度由之前开始相对差异变为非常相似的过程。

May, 2000

本文介绍了一种使用浓缩哈希算法来加速模型计数问题的近似计数算法，实验结果表明使用浓缩哈希算法可以显著提高算法的速度。

Apr, 2020

这篇研究报告讨论了如何解决 NP-Complete 决策问题中的 “相位边界” 问题，介绍了在 K-SAT 中发生的相变的解析解和实验研究。其中，在计算代价随问题规模呈指数级增长的情况下，首次发现了 “随机一阶相变” 的本质，并提出了可能的搜索启发式算法改进方案来应对决策问题中的 “脊骨”。

Oct, 1999