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

Jul, 2015

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

Feb, 2016

本文系统研究了系统地计算计算群体重建的广泛范围复杂性问题。研究的问题可以描述为约束满足问题，其中约束对根三元组关系具有一阶定义。作者证明了每个此类计算群体重建问题可以在多项式时间内解决或为 NP 完全问题，并提出了通用的多项式时间算法解决根三元组一致性问题。作者认为这个分类对通用代数，模型理论和拓扑学是独立而有价值的。

Mar, 2015

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

Dec, 2007

本研究提出了一种基于线性规划松弛的计算方法，用于解决在有价约束语言下的约束最小化问题，包括子模型、双子模型以及树状子模型等。

Apr, 2012

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

Jun, 2008

研究定值约束满足问题，利用基本线性规划松弛和对称分数多项式的精确代数刻画，实现了多个类的问题的可处理性，包括在任意格上子模的问题，任意有限域上的 k - 子模问题，任意树上具有弱（hence 强）树子模的问题。

Nov, 2013

研究了约束满足问题中基本关系具有小拼接性质的 CSP，提出了一种求解这类问题的算法，时间复杂度为 f (w)・n^{O (1)}，并且不仅限于二元约束。

Jul, 2021

本文通过构造极难的 CSP（具有大域）和 SAT（具有长子句）例子，证明这些例子无法在不进行详尽搜索的情况下求解，从而得出 P≠NP 的结论，这种建设性方法对证明不可能性结果非常不同，并且缺少计算复杂性理论中当前使用的方法。

Feb, 2023

本文证明了 Feder 和 Vardi 提出的关于非统一约束满足问题的复杂度的分裂猜想。

Mar, 2017