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

Nov, 2006

该综述从物理学角度介绍了用于解决组合优化问题的工具和概念，特别是与相变以及统计物理学相关的部分，并给出了物理学对计算机科学的跨学科贡献的观点。

Apr, 2001

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

Dec, 2007

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

Apr, 2017

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

Mar, 2015

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

Feb, 2016

本论文研究了通过机器学习解决 NP 困难问题的可行性，指出了训练数据的易变性及其对模型的影响，并提出了改进的方法来适应这个问题。该方法被应用于非线性、非凸、离散组合问题的求解，取得了有效的结果。

Jun, 2021

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

Dec, 2006

通过系统的约束求解器的黑盒方案，结合搜索空间的统一探索，我们提出了一种新的采样技术，可以克服采样过程中的诸多困难，形成了自然的近似模型计数技术。

Oct, 2012

本文报告了一种可精确求解的随机子立方模型，该模型以硬约束满足和优化问题的结构为灵感，复现了随机 k - 可满足和 k - 着色问题的解决方案空间结构，并经历了与这些问题相同的相变。

Oct, 2007