基于interaction和backbone的NP类MAS问题解集表示、复杂性统计与高效算法研究

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.

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

NP问题的解集结构复杂性征是计算复杂性研究领域的核心研究难点之一,目前研究表明该问题与复杂系统相变理论和NP问题的高效求解算法研究有着密切的联系。已有的研究结果大多是从统计物理角度对NP问题的复杂解集结构进行探索，缺乏强有力的严格理论支撑和数学证明，本项目瞄准这一科学问题并围绕MAS问题及与之强相关的Vertex-Cover问题、SAT问题等，以解集表示及结构特征统计、相变相关理论研究、复杂性度量研究、解集的动力学逼近方法、基于解集典型结构的高效算法设计为主要研究内容，展开相关研究并进行了成果应用。首先，结合backbone研究了NP问题中变量之间的互相影响关系，基于这一精细刻画分析得到了以顶点覆盖问题的解集一般表示方法，并针对该解集的结构特征，探索了与之相关的#P问题；其次，针对相变理论，以渗流相变作为基本研究对象，分析了不连续性相变的产生机理和产生多个巨大连通分支的充分条件；再次，针对树、二分图、无摘叶核图等简单拓扑结构，研究了其上的解集结构特征并进行统计分析，认知了NP问题相关算法设计的难点；然后，定义了一种变量关系耦合的复杂性度量——奇数圈中心性，将之与最大匹配问题结合起来分析得到了一种动力学逼近解集的理论和相关算法；最后，将研究所得理论成果应用于煤矿安全监测监控取得良好效果。本项目的研究内容和所取得的成果，是对于计算复杂性理论和NP问题复杂性根源的深入研究，能够对多角度认知复杂性本质特征、揭示结构复杂与计算复杂关系、设计NP问题高效求解/近似算法提供重要的理论支撑，推进对P=？NP这一世界难题进一步认识。

内容获取失败，请点击重试