基于空腔方法的随机约束满足问题相变复杂性与高效算法研究

The phenomenon and mechanics of phase transitions in random constraint satisfaction problems is the key to explore the nature of hardness in NP-complete problems. Previous researches are focused on random constraint satisfaction problems with fixed domains in which the domain size of each variable is independent of the problem size. In this project, we study a representative random constraint satisfaction problem with growing domains. Using the cavity method in the field of spin glass from statistical physics in disordered systems and rigorous mathematical tools, we investigate the various structural phase transitions in the solution space of the problems, and we analysis the complexity of these transitions. By identifying critical behaviors in the evolution of solution space, we develop efficient heuristic message-passing algorithms to find solutions of random constraint satisfaction problems with growing domains. Therefore, we can establish the fundamental theory frame for solving these random constraint satisfaction problems with growing domains. These studies can precisely describe the phase diagram of the set of solutions of the random constraint satisfaction problems with growing domains as the control parameter increases. Moreover, we performed the algorithms to verify the locations of the transition thresholds obtained rigorously. We hope that these results can provide new insights into the understanding of the onset of computational hardness in NP-complete problems, and the algorithms can be useful for solving practical problems in technological applications.

随机约束满足问题的相变现象及其形成机制是探索NP-完全问题难解本质的关键之一。基于目前在具有固定取值域的随机约束满足问题上已经取得的理论研究基础，本项目针对一个典型的具有增长取值域的随机约束满足问题，引入随机无序系统中自旋玻璃理论的空腔方法，结合组合数学与概率方法等数学工具，对问题解空间的各种结构性相变现象及其复杂性成因进行研究，并进一步利用解空间的统计特征和分布规律，开发能够处理变量取值域可变的随机约束满足问题的高效、可靠的算法及其实现机制，从而建立起求解此类随机约束满足问题的基本理论框架。此外，本项目将分析具有增长取值域的随机约束满足问题的相变机制与具有固定取值域的随机约束满足问题相比所表现出的新特性，并阐述相变复杂性与求解算法之间的内在联系。这些研究结果将能更好地促进对NP-完全问题难解性的全面理解，同时对计算应用中可以归约为具有可变取值域的随机约束满足问题的求解具有一定的指导意义。

随机约束满足问题的相变现象和高效求解算法是计算复杂性理论的研究热点和难点。以前对约束满足问题的研究主要集中在具有固定取值域的模型上（如k-SAT等），本项目则对一个典型的具有可变取值域的随机约束满足问题即RB模型的相变复杂性和高效算法进行了研究。理论上，提出了RB模型的两个推广模型，分别为RB^{mix}模型和p-RB模型，这两个模型分别是RB模型在约束长度和约束紧度上的推广。已经严格证明在满足一定条件下，这两个模型都具有精确的可满足性相变现象，并且从实验上已经证明在相变阈值附近，RB^{mix}模型的求解难度随着问题规模的增加而呈指数级增长。这两个模型既具有精确相变又能产生难解实例，对随机约束满足问题的算法测试具有重要的意义。算法上，首先提出了两个基于模拟退火的改进算法即RSA（Revised simulated annealing algorithm）和GSA （Genetic-simulated annealing algorithm）。在RSA算法中，将温度控制引入到对随机化初始赋值的扰动策略中；而在GSA算法中，利用改进的遗传算法来得到初始解。数值结果表明：在约束紧度进入相变区域时，这两种算法都可以有效地找到RB模型随机实例的解。在临近相变点时，虽然算法失效，但是得到的最优解仅使得极少数的约束不能满足。其次将RSA算法应用于由BP（Belief propagation）引导的消息传递算法得到的最优解的值修正阶段，提出了BP-RSA算法。这些算法的提出对具有大值域的随机约束满足问题的求解具有重要的理论价值和实际意义。