非固定值域随机约束满足问题的解空间结构与求解算法研究

The computational complexity and phase transition phenomenon in random constraint satisfaction problems is an important way to study the NP complete problems. This project aims to study a class of constraint satisfaction problems with unfixed domains by using rigorous mathematical analysis and statistical-mechanic tools. We investigate the various structural phase transitions of the solution space as the control parameter increases, and design efficient heuristic algorithms to solve random instances. Combined with previous results on constraint satisfaction problems with fixed domains, we can sum up the structural characteristics of all constraint satisfaction problems. Our results on structural changes in solution space and designing algorithms will help understanding the intrinsic hardness in NP-complete problems, and is of theoretical value to design efficient algorithms in real problems.

随机约束满足问题（CSP）的计算复杂性及相变机制的研究是探索NP完全问题难解之谜的重要途径。本项目旨在利用数学及物理的理论方法，研究一类非固定值域随机约束满足问题模型在约束强度增加过程中解空间结构发生的一系列相变现象；结合这些结构特征设计出高效的求解算法；根据已有的参数固定型随机约束满足问题模型的研究结果，探索随机约束满足问题解空间的总体结构特征。本项目在解空间结构和求解算法等方面的研究，不仅有助于从理论上理解NP完全问题难解的本质原因，而且对设计算法求解现实问题有重要的指导意义。

随机约束满足问题（CSP）的计算复杂性及相变机制的研究是探索NP完全问题难解之谜的重要途径。本项目旨在利用数学及物理的理论方法，研究一类非固定值域随机约束满足问题模型在约束强度增加过程中解空间结构发生的一系列相变现象，探索随机约束满足问题解空间的总体结构特征。本项目主要围绕一些经典随机约束满足问题模型的精确相变问题和解空间结构问题等取得较好的成果。具体有：提出了新的约束满足问题模型-(3+p)-SAT，研究其更具稳定性的(1,0)-超解的相变问题；优化了随机MAX 3，4-SAT模型的p可满足阈值点；研究了随机d-k-CSP模型和RB模型的解空间结构；研究了由2-边和3-边构成的超图的传播连通性；利用物理中的空腔方法研究了随机2-SAT的解的个数。本项目的研究成果不仅有助于从理论上理解NP完全问题难解的本质原因，而且对设计算法求解现实问题有重要的指导意义。