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

Apr, 2017

本文研究了扩展时序约束问题的复杂性，并针对一组量词自由的 “小于等于（leq）” 公式所形成的 Poset-SAT 问题进行了讨论。其问题是对于 $x_1$，$x_2$，…，$x_n$ 成为偏序集时是否存在满足给定公式的赋值。最后，作者使用模型理论概念和通用代数技术研究了这些问题的约束满足问题，并提出了独立于通用代数和模型理论的分裂定理。

Feb, 2016

通过采用玻璃体系的空腔方法，我们在随机可满足性和随机图着色问题中，探讨困难问题的算法性质以及所谓的冻结变量的存在与问题的难度之间的关系，从而引入一个新的 “锁定” 约束满足问题的类别。

Jun, 2008

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

Nov, 2006

本研究基于四元组和直接映射两种编码方式，考虑了通过答案集编程解决超级树（supertree）构建问题的方法，并采用这两种编码方式构建出了家猫属（Felidae）的属级别超级树，在与 MRP 方法构建的超级树进行比较后得到了相关结果。

Jul, 2015

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

Dec, 2007

本文研究二元量化约束满足问题的混合可处理性，利用破坏三角形性质识别了一类基本的可处理问题，通过引入破坏角度约束，打破了变量排序的限制，进一步识别出一些新的可处理问题，并最终确定了更广泛的可处理类型，即 QCSP 的 min-of-max 可扩展类。

Apr, 2011

在平面图情况下，我们证明了与各种满足性、图形和组合问题相关的计数问题的 #P 难度。另外，当局限于计划实例时，我们证明了具有不明确解决方案性的满足性问题的 NP 完全性和与唯一满足性问题相关的随机多项式可简化的 DP 完全性。假设 P≠NP，则以上结果的一个推论是：不存在 ε- 逼近算法，用于在整数上计划线性不等式约束系统的最大化或最小化线性目标函数问题。

Sep, 1998

证明了对于约束满足问题的近似版本，线性规划松弛的规模存在超多项式下界，并且对于这些问题，多项式大小的线性规划方案与一定轮数的 Sherali-Adams 层次中产生的方案具有相同的能力；具体来说，最大割的多项式大小线性规划的可积性差可能性上界为 1/2，而最大三种满足问题的多项式大小线性规划则可能性上界为 7/8。

Sep, 2013

本文介绍了一个算法，用于找到具有给定列表中的类中的离散类的强后门，这些类由 CSP 实例中的连通分量确定，并表明满足特定条件时，可以通过这种方式超越 CSP 的易处理性限制。

Jul, 2015