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

项目名称： 量化约束满足问题相变现象研究

项目编号： No.61503074

项目类型： 青年科学基金项目

立项/批准年度： 2016

项目学科： 其他

项目作者： 王佳男

作者单位： 东北师范大学

项目金额： 22万元

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

中文关键词： 量化约束满足问题；相变现象；随机约束可满足；可满足性；问题结构

英文摘要： 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.

英文关键词： Quantified Constraint Satisfaction Problem;Phase Transition;Random Constraint Satisfaction;Satisfiability;Problem Structure