论文部分内容阅读
K-SAT问题是计算复杂性研究领域的中心问题之一。它是关于一类逻辑运算方程组是否有解的判定问题，K-SAT问题是Cook在1971年提出的第一个NP完全问题。
数值模拟显示，维持方程组个数和变量数的比值一定，当方程组规模趋于无穷大的时候，随机K-SAT问题，即其方程组是以一个特定的随机模式构造的，表现了一种特定的相变情形。目前，该相变值的存在性已经得到数学的证明，但是其具体求值仍旧是非常困难的。
Monasson和Zecchina将统计物理的SpinGlasses理论引入对随机性K-SAT问题的研究，使得前文中所谓的求值成为可能。但是，这种方法的严密性还需要数学上的进一步工作。
在本文中，我们构造了一个新的模型，它集中于讨论“最优解”部分。我们希望通过对它的分析，能够揭示更多的关于相变现象的成因。