在物理学史的大多数时期，科学家们研究完全有序的系统，如对称的晶体；或者完全无序的系统，如理想气体。然而在七十年代早期，他们不得不开始面对介于上述两者之间的系统——无序”系统。自旋玻璃(Spin Glass)理论是了解无序系统最成功的尝试之一。如今，研究自旋玻璃而发展起来的技术已经被用于诸如计算机科学、神经学、生物学和经济学等若干领域，可以说自旋玻璃是研究复杂系统的基础理论之一。　　 本文主要探讨自旋玻璃在组合优化问题的应用。组合优化问题是从实际应用中抽象出来的计算机问题，一直以来该领域的计算机科学研究集中于寻找最有效的求解算法。在此过程中，人们发现在某些特定的参数值附近，求解时间和解空间的结构会发生很大的变化，这与物理系统的相变现象很相似，也正是统计物理方法得以涉足的主要途径。　　 第一章至第三章首先简要回顾了近几十年发展起来的自旋玻璃平均场理论，包括早期的副本方法(replica trick)和随后建立的空穴场方法(cavitymethod)。接下来几章通过建立合适的自旋玻璃模型，将上述理论应用于各种组合优化问题，分析它们解空间的性质。　　 第四章研究一阶副本对称破缺(1RSB)近似下的组合优化问题——顶点覆盖和K-SAT问题的空穴场分布。作者通过有限温度空穴场方法的零温近似得到空穴场方程组，这样使得分析系统平衡时是否存在分数空穴场成为可能。通过种群动力学方法求解，作者发现1RSB近似下空穴场存在分数值。并且，作者进一步分析了分数空穴场比例随温度参量y、平均连通度c(或约束密度α)的变化关系，这种分数场的存在暗示宏观热力学态具有更高级的结构。　　 第五章研究各态历经破缺热力学态的自由能分布。人们通常认为对于各态历经破缺的热力学系统，其平衡态性质由最低自由能态决定，且自由能服从指数分布。作者的研究表明，事实并非完全如此。相反，对某些复杂系统，在一定的温度范围内，其平衡自由能将服从高斯分布。与此同时，系统的统计物理性质将由能量较高的激发态决定。　　 第六章研究K-SAT问题解簇的统计物理性质。作者将研究视野转到解空间的局部区域——解簇。一方面，作者指出导致凝固变量的两种机制。第一种机制可由whitening算法分析，作者建立了解簇内凝固核大小的平均场理论，该理论与相应whitening算法的实验结果相符，理论证明了凝固变量存在与否完全取决于强约束(即仅含一个满足变量的约束)密度。第二种机制源于系统的长程阻挫性质，作者提出一个启发式算法SpinFlip搜索因此产生的凝固变量。另一方面，长程阻挫可导致熵信息传递(entropic belief-propagation)方法不收敛，作者在迭代过程中基于whitening算法固定部分变量并计算了待考查解簇的熵密度。结果表明survey-propagation算法和WalkSAT算法给出的解既不位于最大熵密度解簇也不位于具有最多相同熵密度解簇的那一类解簇内部。　　 在最后一章作者对本论文做了总结和展望。