自从Steve Cook证明了第一个NP完全问题以来,大量的NP完全问题不断被发现,而且很多问题具有重要的实际应用。比如,SAT问题是大规模集成电路自动布线和人工智能领域的关键问题,着色问题在组合优化、规划调度等方面有着广泛应用,子图同构问题是模式匹配中的核心问题,子集和问题可以应用于公钥加密。是否存在能够多项式时间内求解NP完全问题的确定性算法(即是否NP=P),是理论计算机领域多年悬而未决的难题。无论NP=P抑或NP≠P,对NP完全问题的研究都能促进人们加深对此类问题乃至人类思维过程的理解。近年来越来越多的学者开始从算法的实用性角度质疑P与NP问题的价值,比如Knuth就指出,“就算NP=P,仅仅知道一个问题有多项式时间算法是没有实际意义的,因为那个指数可能大得超过计算能力,因此也许我们从一开始就不应该提出P与NP这个糟糕的问题。”[56]尽管如此,P与NP问题作为千禧年七大难题之一仍然是理论计算机科学的圣杯[57]。近几年,每每有人提出P与NP问题的证明,总能引起学界和社会上的热烈讨论,这足以说明人们依然十分关注这一基本问题的研究动向。P与NP问题看起来很容易却又难以着手,每当人们以为即将解决它时却又发现总因遇到绕不过的障碍而不得不回到原点。这导致了这一问题提出近50年至今仍然没有太大进展。文献[1]针对一种称为MSP问题的新的NP完全问题,提出了一种名叫Z-H算法的多项式时间求解方案,为NP完全问题的研究提供了新的着力点。相关结果已于2010年向Transactions on Algorithms投稿,评审至今没有发现问题。自2010年下半年至2014年上半年,已产生了5300万例MSP问题随机实例以测试Z-H算法,无一出错。但是,当前对于MSP问题的NP完全性研究工作还刚刚起步;而且目前Z-H算法只能求解小型实例,如何对算法进行充分测试成为难题。本文依托国家自然科学基金项目“NP完全问题求解复杂性研究”,从多个角度深入研究MSP问题的特性,并在此基础上设计了大量针对Z-H算法的测试方案。主要工作如下:1.基于问题归结研究了MSP问题与SAT、着色、子图同构、哈密顿回路、团、子集和问题的对应关系(其中子图同构和子集和问题的归结是第一次给出),揭示MSP问题所反映的NP完全问题的共性及其作为NP完全性模型的强大表达力,为利用其他NP完全问题迥异的实例结构深入测试Z-H算法作了铺垫。2.通过实验观察到了MSP问题在特定区域上有解实例比例和Z-H算法平均求解时间的相变现象。这是继回溯、概率搜索等算法之后,又一种新的算法框架被发现存在相变,印证了相变属于问题内在属性而与算法无关的猜想[61]。确定了MSP问题的相变序参量和相变点,初步估计了解的存在性临界值。利用MSP问题的相变模型,能够对Z-H算法作进一步测试。3.由于Z-H算法思想基于直觉形象而非分析解构,针对具体多级图实例的Z-H算法执行过程(特别是Change算子)非常复杂,每一步操作的边数之多使得想要通过机械地人工计算来摸透算法内涵几乎不可能,因此以往的研究都只能笼统地给出算法的大致思想而没能分析具体实例[54,55]。本文利用鸽笼公式实例的良好结构特性以及从SAT问题到MSP问题的归结,结合手工推导和机器计算,第一次清晰地给出了较大问题规模下的算法运行特征分析。4.反复研读、推敲和讨论了Z-H算法的正确性证明。提出了针对撕裂证明的实例合并测试方法。实验证明已经测试多年的现有代码[1,55,62]存在漏洞,从而表明了合并测试方法的有效性。依据已有的严格数学证明[1],我们认为Z-H算法本身仍然是正确的。5.设计实现了基于Z-H算法的NP完全问题通用求解器。一方面可以用来求解多类NP完全问题;更重要的是,以往的Z-H算法测试都是针对小规模的随机MSP实例,利用上述问题求解器,可以利用归结、相变和合并构造等对Z-H算法进行更大强度的测试。在本文作者的课题组和北航许可教授的努力下,共同完成了以上测试。