NPC问题算法复杂性相变现象，特别是解集的clustering和backbone等拓扑结构对算法复杂性的影响是国际前沿热点方向，然而已有研究基于大量非严格性经验假设，使得复杂性相变结果的准确性难以保障。申请人致力于建立复杂性相变的严格分析方法，构建了具有显著代数特征的NPC问题-有限域MAS模型，得到其解集代数生成元统计和相变点严格界估计，并提出interaction结构特征成功应用于顶点覆盖问题。为了深入研究相变的数学特征及其算法意义，本项目拟利用腔方法和状态更新方程动力学分析典型结构演化，并结合随机图、复杂网络与代数统计，研究MAS问题解集表示方法及其动力学获取/逼近、解集结构特征统计与复杂性关系、基于解集结构特征高效求解算法设计，通过归结降维、摘叶消元、等价代换等思想构造该类问题的高效求解算法，建立一种新的研究NPC问题复杂性相变规律的方法及面向解集典型结构特征的高效求解算法策略。

Phase transition of algorithm complexity of NPC problems, especially the influence of clustering and backbones to algorithms is a hot topic for international researches, but previous results perform not exact for the inexact assumptions. To construct strcit methods for the phase transitions of computational complexity, we have built a MAS model of finite field which is NPC and has distinct algebraic characteristics, obtained its generator statistics of solution spaces and bound estimations of its phase transition points, and proposed the interaction structure with successful applications on the vertex-cover problem. In order to perform further researches on the mathematical characteristics and algorithmic significance of phase transition, based on the evolution of interaction and backbone structures, and using the cavity method and dynamical analysis of status update equations with random graph theory, complex networks and algebraic statistics, in this project we study the expression of the solution space with its dynamical acquisition or approximation, statistics of solution space structures with the algorithmic complexity, and effective algorithm design based on the solution space structures. The algorithmic strategies are constructed by reducing dimensions, leaf removal and variable equivalence replacement, which will provide a new mathematical method to study the complexity phase transition of NPC problem and effective strategies to solve the NPC problem by the typical structures of solution space.