● 摘要
“NP vs P”是世界七大数学难题之一。 NP-完全问题自提出以来就迅速成为国际学术界相关领域内备受瞩目和广泛研究的热点问题，同时也是数学界、理论计算机科学界和统计物理学界面临的一个巨大挑战。一般情况下，大多数的随机约束满足问题都是NP-完全问题。因此，对随机约束满足问题进行深入系统的研究不仅有助于从理论层面上探索NP-完全问题难解性的本质根源，而且对工程技术应用中可以归约为约束满足的问题具有极其重要的指导意义。本文应用严格的数学理论分析方法和统计物理中自旋玻璃理论的复本方法（replica method）和空腔方法（cavity approach）来研究一类具有可变取值域的随机约束满足问题。特别地，针对一个典型的具有增长取值域的随机约束满足问题即RB模型，分别从相变行为的复杂性分析和高效的启发式算法设计这两个方面进行了一系列广泛深入的探索性研究，进一步刻画了问题解空间的结构特征和演化规律，为最终揭示相变区域涌现出大量难解实例的本质原因奠定了良好的基础。主要工作包括：提出具有混合不同长度约束和一种全局约束（all-different global constraint）的RB^{mix}模型。通过严格的数学方法分析证明，与具有等约束长度的RB模型相比，混合约束并没有改变可满足性相变现象的本质特征，即RB^{mix}模型不仅存在可满足性相变现象，而且可以得到与RB模型相同的精确相变点。这些结果能更好地促进对NP-完全问题相变机制的理解，同时对设计高效的求解算法也具有一定的理论指导意义。通过引入统计物理中有限尺度分析方法，研究了在有限尺度效应（finite-size scaling effect）下，RB模型相变行为的基本特征。分析了随着系统规模的不断增加，相变发生区域的变化规律。从理论上给出了系统规模在实现从有限到无穷时，RB模型相变区域的尺度窗口（scaling window）的上界。这一项研究成果也是国际上第一次围绕NP-完全问题的尺度窗口进行的严格分析，为今后更好地研究和理解NP-完全问题的相变现象及其难解本质奠定了良好的基础。针对一类具有可变取值域的随机约束满足问题，提出基于信息传播机制的启发式不完备算法，深入研究问题解空间组织结构的演化规律。首次突破性地将统计力学中的自旋玻璃（spin glass）理论应用到具有可变取值域的NP-完全问题中，并设计了由Belief Propagation（BP）引导的消息传递算法。在算法消去变量的过程中，分别采取了最大概率分量、最小分量熵、最小变量熵等策略来对变量进行固定赋值，并通过对运行时间、变量熵、变量的平均自由度等统计特征量的分析，阐释了算法能在具有大规模取值域的随机约束满足问题上高效求解的运行机理。从算法角度刻画了可满足性相变现象的基本规律，探索了相变行为复杂性的形成机制以及相变区域大量涌现出难解实例的本质根源。应用统计力学中自旋玻璃理论的空腔方法和数学中严格的概率方法，从数理结合的角度研究了具有可变取值域的随机约束满足问题，重点探讨了解空间的统计特征和分布规律。理论上，通过用Hamming distance度量解对间距离的变化，阐述了解空间从连通的单态解集分裂为不连通的解簇这一动力学演变过程。实验上，提出了针对具有可变取值域规模的随机约束满足问题的Reinforced BP算法，数值结果表明这是目前已知的性能最为优越的求解算法。通过比较BP熵和系统熵、算法效率的突变点和严格的理论分簇点，发现这些统计量以及特征量几乎完全吻合。同时，Reforced BP算法也可以广泛地应用到具有大规模取值域的约束满足问题上。 这必将对推动融合数学上严格方法和物理思想来研究NP-完全问题中各种相变形成机制以及揭示其复杂性本质成因产生较大的影响。