● 摘要
随机K-SAT问题是理论计算机科学的一个重要研究领域. 伴随着随机K-SAT的可满足性相变，发生了一种简单搜索算法的计算成本上的相变. 这种几乎同步的相变出现在一大类的NPC问题中，这种巧合激发了研究人员对于NPC问题的结构，演化以及其对计算模型的适应性的探索.本文第一部分结果讨论在随机K-SAT的可满足相变问题中, 其解空间随着序参数演化的过程；提出了相变点附近的一种新的典型结构---长程等价类；并把这种等价类的思想应用到扰动图中, 指出等价的自旋顶点在扰动图中将会形成环状结构, 由此解释了研究人员关于扰动图中的圈的长久猜测：扰动图中的大尺度的圈的出现, 是致出现计算上的相变的一个可能的重要原因. 进一步, 本文对大尺度局部交互作用的粒子系统的一般性相变理论进行了讨论, 得到了更为一般的Gibbs测度唯一性的判别准则. 在 Weitz 和Winkler的工作的基础上, 我们利用路径耦合的方法, 把Dobrushin的点对点（通过点构建）的影响推广到块对块（通过块构建）的形式. 在此提出的唯一性条件和空间相关退化的概念是紧密联系的,并且我们定义的影响的度量包含了之前Dobrishin和Weitz定义的度量. 本文共分四章．第一章介绍了随机K-SAT问题及其同步相变现象, 讨论相变点附近简单搜索算法的计算成本突然增加的可能原因.第二章是第三章的理论基础，介绍了平衡态统计物理方法在组合优化问题分析中的应用.第三章是我们的第一部分结果, 我们用Cavity Method 在 RS 层次上对构建在随机图上的极小顶点覆盖问题和随机K-SAT问题中的等价类的划分进行了研究, 计算了此类系统在相变点附近的解空间出现的一种新的典型结构，即长程等价类．第四章是我们的第二部分结果，主要对大尺度局部交互作用的粒子系统的一般性相变理论进行了讨论, 得到了更为一般的有限/无限图上的Gibbs测度唯一性的判别准则.