量化约束满足问题相变现象研究

In the past decade, we have viewed great success in the problem of phase transition of constraint satisfaction problem (CSP for short). However, the research of phase transition of Quantified constraint satisfaction (QCSP for short) problem is still in its bottleneck stage. Until now, the phase transition point of QCSP is still unknown, the relationship between phase transition and problem structure is not constructed, and the algorithms to solve hard instances in phase transition is few. Thus in the project, we shall study the phenomenon of counting satisfaction problems of different random model. First of all, we shall prove the existence of phase transitions and obtain the location of phase transition thresholds in QCSP. Then we shall study the structure of the problems to provide theoretical evidence of the intractability of the random instances around the phase transition thresholds. Finally, we shall develop efficient algorithms to solve hard instances around the phase transition threshold based on above analysis.

尽管对经典约束满足问题相变现象的研究已经取得了令人瞩目的成绩，但迄今为止，对量化约束满足问题相变现象的研究尚存在瓶颈。对于一般的随机量化约束满足问题模型（如RB模型等），尚未确定其相变点位置，也未能建立问题结构与相变现象、难解性之间的关联，目前缺乏针对一般的量化约束满足问题相变区的有效求解算法。因此本项目将围绕量化约束满足问题的相变现象这一核心内容开展研究：证明量化约束满足问题中相变现象的存在，并确定其相变点位置；研究问题结构特征与相变现象之间的关系，为量化约束满足问题的难解性提供理论证据，并从中确定影响量化约束满足问题相变现象的结构特征；通过对算法在相变临界区失效的原因进行分析，有针对性的设计高效的量化约束满足问题求解算法。

本项目围绕量化约束满足问题等难解问题的相变现象这一核心内容开展研究：证明这些问题相变现象的存在，并确定其相变点位置；研究问题结构特征与相变现象之间的关系，为这些问题的难解性提供理论证据，并从中确定影响相变现象的结构特征；通过对算法在相变临界区失效的原因进行分析，有针对性的设计高效的难解问题求解算法。项目组在AAAI、IJCAI等国际权威会议、《Science China Information Sciences》、《Information Science》等国内外权威期刊发表学术论文13篇，包括中国计算机学会推荐A类会议论文4篇，中国计算机学会推荐B类期刊论文3篇，SCI期刊检索论文8篇。