中文摘要：

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