研究了如何利用命题可满足性 (SAT) 解决比 NP 或 co-NP 更困难的问题，特别是对命题析取答案集编程中的基本推理问题进行探讨，介绍了利用新的 Parameterized Complexity 技术从 Brave 和 Skeptical Reasoning 转换到 SAT 的方法。

Jan, 2013

本文提出了一种新的问题转化方法，将 CNF 公式的决策问题转化为 Horn 公式的最大可满足性问题，并证明了在鸽笼公式的情况下 MaxSAT resolution steps 的数量存在多项式绑定。

May, 2017

该论文研究了基于约束满足问题的自然组合问题如何表达的问题，分类了可在多项式时间内解决和 NP 完全的子类，并从约束语言的角度提出了一个算法来解决约束满足问题。

Apr, 2017

介绍一种用几何模型来解决多约束条件优化问题的方法，并在布尔可满足性问题和球体堆积问题两个基准测试中说明了其有效性和竞争性。

Dec, 2007

本研究提出了 G2SAT 这一深度生成式框架，可以学习从输入公式集生成满足真实世界 SAT 实例特征的 SAT 公式，旨在扩展现有的数据集，为 SAT 求解器的性能提供优化方案。

Oct, 2019

本研究基于 “最小不可满子集” 算法构建了一种寻找满足给定成本度量的最佳不满足子集的算法，并开发了加速解释序列生成的方法，实验证明，该算法在解释质量和计算时间方面比 “最小不可满子集” 方法更优。

Mar, 2023

利用图神经网络训练适用于布尔可满足性问题的 SLS 求解器，可显著提高性能，平均解决比例更高、步骤更少，具有性能保证。

Sep, 2023

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

Sep, 2005

本论文研究了使用随机局部搜索解决基于满足性问题的 SAT 问题的流行范式，以及通过学习逻辑蕴含来改善求解器性能，并提出了一种生成逻辑等价问题形式的方法，进一步深入研究学习逻辑蕴含如何影响 SLS 运行时间的问题。

Oct, 2022

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

Oct, 1999