P与NP问题研究_杜立智

1、第 23 卷 第 1 期计 算 机 技 术 与 发 展Vol 23No 12013 年 1 月COMPUTER TECHNOLOGY AND DEVELOPMENTJan2013P 与 NP 问题研究杜立智，符海东，张 鸿，黄 林( 武 科技大学 算机科学与技 学院，湖北 武 430065)摘 要: P 与 NP 问题被列为七大世界数学难题之首，由于其相关概念抽象而复杂，许多该领域的学生学者，对其相关概念的理解存在谬误，不少已发表的研究论文都体现了这一谬误。用中文通俗讲解到底什么是 P 和 NP 问题以及它们的关系，透过抽象的定义揭示其本质。列举一些科研论文上常见的对 P 和 NP 问题理解上

2、的谬误，通过分析揭示其错误实质。同时并对解决这一问题可能的研究方法作一综述，对研究前景做一展望，为在该方向上学习和研究的学生学者，提供有价值的参考。由于文中包括: 对复杂抽象的概念进行通俗而深入的剖析，对已有的研究进展进行摘要概括，对未来可能的研究方法和研究路线进行综述和分析，故能对该领域的研究者在概念的正确把握、文献的查阅和研究方向的选择上提供助益。关键词: 七大数学难题; 确定性图灵机; 非确定性图灵机; NP 完全问题中图分类号: TP31文献标识码: A文章编号: 1673 629X( 2013) 01 0037 06doi: 10 3969 /j jssn 1673 629X 201

3、3 01 010A Study of P vs NPDU Li zhi，FU Hai dong，ZHANG Hong，HUANG Yuan lin( College of Computer Science and Techn ，Wuhan University of Science and Techn ，Wuhan 430065，China)Abstract: P versus NP is the first one of the famous seven great mathematical problems in this world Because the concepts about

4、them are very abstract and complicated，some scholars and students in computer science often misunderstand them A lot of published papers con-tain these misunderstandings It explains these concepts in Chinese clearly By deeply studying their definitions，reveal their essence List a lot of misunderstan

5、dings of these concepts and analyse them Also survey the research methods and foresee the research future of this field，so as to give an assistance to this fields people It contains: to analyze the complex and abstract concepts in an easy way，to pick up important points from a lot of products，to sur

6、vey and analyze the methods for the future study，so it can help the researchers in this field for all the above aspectsKey words: the seven great mathematical problems; deterministic turing machines; nondeterministic turing machines; NP complete prob-lems0引言2000 年，美国克莱数学研究所公布了世界七大数学难题，又称千禧年大奖难题，规定对每

7、一难题的破解者颁发一百万美元的奖金。其中 P 与 NP 问题被列为这七大数学难题之首，从而大大激发了对这一问题的研究热情。然而，由于 P 和 NP 问题及其相关概念相当抽象而复杂，加之这类问题的原创在国外，一些翻译过来的相关书籍往往表达不准确，甚至出现翻译错误，使得许多研究这个问题的中国学者以错误的概念为基础，更不谈相关专业的本科生研究生对这些概念缺乏真正准确的理解了。例如，不难在一些教材或科研论文上找收稿日期: 2012 04 12; 修回日期: 2012 07 18基金项目: 2010 年国家自然科学基金青年基金项目( 61003127)作者简介: 杜立智( 1964 ) ，男，副教授，硕

8、士，研究方向为计算机算法、人工智能。到这样的错误提法: 由于某问题是 NP 问题，故不可能有多项式时间算法，云云。甚至一些有一定档次的科研论文通篇都建立在错误的概念的认识上。文中的目的是，用中文通俗讲解到底什么是 P 和 NP 问题以及它们的关系，透过抽象的定义揭示其本质。列举一些科研论文上常见的对 P 和 NP 问题理解上的谬误，并通过分析揭示其错误实质。同时对解决这一问题可能的研究方法作一综述，对研究前景做一展望，为在该方向上学习和研究的学生学者，提供有价值的参考。由于文中包括: 对复杂抽象的概念进行通俗而深入的剖析，对已有的研究进展针对大量的研究文献进行摘要概括，对未来可能的研究方法和研

9、究路线进行了综述，并加进了自己的深入分析，故能对该领域的研究者在概念的正确把握、文献的查阅和研究方向的选择上提供助益。38计算机技术与发展第 23 卷1 通俗详细地讲解什么是 P 和 NP 问题以及它们的关系要计算或解决一个问题，该问题通常有一个大小规模，用 n 表示。例如，若分析计算一个二进制数，该数有多少位，这个位就是其大小规模。再比如，从 n 个数里面找出最大的那个数，这个 n 就是该问题的规模大小。怎么找?要比较 n 1 次才能得到结果，这个 n 1 就是所花的时间，也就是时间复杂度。再比如，将 n 个数按从大至小排序，n 是其规模大小，若是按这样的方法: 第一次从 n 个数里找最大，

10、第二次从 n 1 个数里找最大，以此类推，需要的比较次数就是 n( n 1) /2，称所用的方法为算法，称 n( n 1) /2 为该算法的时间复杂度。对于时间复杂度，当 n 足够大时，只注重最高次方的那一项，其他各项可以忽略，另外，其常数系数也不重要，所以，n( n 1) /2 只重视 n 的平方这一项了，记为 O( n 的平方) ，这就是该算法对该问题的时间复杂度的专业表示。所有形如 a* nk + b* n( k 1) + c* n( k 2) 都可记为 O( nk) ，nk 表示 n 的 k 次方，* 为乘号，这样的复杂度称为多项式时间复杂度，若是时间复杂度形如 kn，k 为大于 1

11、的常数，或 n! ，或更大的，就称为指数型时间复杂度。显然，当 n 足够大时，指数型时间比多项式要大得多的多。所有能用多项式时间算法计算得到结果的问题，称为多项式问题，也就是 P，所有绝对不可能用多项式时间求解的可解问题，称为指数型问题。当然，还有一类问题属于不可解问题，也就是说你无论花多少时间1也不能得到解答。有这样一类问题，假使你得到了问题的解，我要验证你的解是否正确，我验证所花的时间是多项式，至于求解本身所花的时间是否是多项式我不管，可能有多项式算法，可能没有，也可能是不知道，这类问题称为NP 问题。NP 概念的奥妙在于，它躲开了求解到底需要多少时间这样的问题，而仅仅只是强调验证需要多少

12、时间，从而为 P 与 NP 这一千年难题的产生埋下了伏笔。显然，P 肯定是 NP，因为你既然能用多项式求解，就肯定能用多项式验证( 难不成我再算一遍! ) ，但 NP 是否是P 谁也确定不了。另外，目前已经很明确的指数型问题也肯定不是 NP2。教科书上关于 P 和 NP 的概念，往往用确定性图灵机和非确定性图灵机来定义，可参阅相关算法教科3书 ，这里不做赘述。问题是这两个定义高度抽象，许多人并没有真正理解透，结果往往是花大力气背了形式上的概念，却丢了本质。不然就不会有不少博士教授在关于 NP 的论文中出现最基本的概念错误。这里解释一下这两者的根本特征及其根本区别。确定性图灵机与现实中单 CPU

13、 的计算机在功能上完全等价，只能进行串行思维，而不能同时并行工作。非确定性图灵机只是一种理论模型，现实中是不存在的。它具有并行工作的能力。完成一件事，要分若干步进行，每一步有多个可能的选择。确定性图灵机在每一步只能选择一个目标，若进行下去后不能达到目的，可返回到这一步，再试另外的目标。而对非确定性图灵机而言，它每一步可以同时选择这一步的所有目标，并行地同时计算下去。所以 P 和 NP 问题的另一种表述是，在确定性图灵机下能用多项式求解的问题就是 P 类问题，而在非确定性图灵机下能用多项式求解的问题就是 NP 问4题 。显然，非确定性图灵机在计算上要比确定性图灵机快得多，高效得多。许多人以此判断

14、 P 不可能等于 NP。这两种定义完全等价。讲到目前为止，NP 的概念还是抽象的，读者恐怕还没有达到透彻掌握的程度。对这样抽象难理解的概念，必须用如下方式去透彻地掌握它:1) 找三个例子，一个为 P，一个为 NP 但不知道是否为 P，再一个为明显的指数型问题比如全排列、汉诺塔等，反复比较理解。2) 尽可能多地找出 NP 问题的特点，哪怕有重叠也没关系，针对每一个特点，结合例子去理解。NP 最显著的特点有两个，一个是分步及每一步的并行性，二就是任何 NP 问题都可转化为是和否的问题，当然，最根本的还有验证多项式。P 和 NP 问题各自都是符合上述定义的那类问题的集合。P 等于 NP 的含义是，这

15、两个集合里面的元素完全相同，也就是说，它们两个根本是同一个集合，否则就是 P 不等于 NP。这两个集合是客观存在的，构成它们的元素在客观意义上也是确定的，但是，由于人类当前的科技认知能力，对某些 NP 问题还不能确定它们是否属于 P，甚至一些问题是否是 NP 也难以确定。正是这一原因导致了 P 和 NP 这一千年世界难题的产生，否则就不会有这一世界难题了。显而易见，这两个集合的关系只有两种可能性，要么相等，要么不等。目前大部分该领域的权威倾向于认为 NP 不等于 P。2 史蒂文 库克与 NP 完全树1971 年，加拿大人史蒂文 库克发现并证明了第5一个 NP 完全问题 ( NPC) ，也就是可

16、满足性问题 。库克证明: 任何 NP 问题都可以在多项式时间内按多项式的规模转化为对可满足性问题的求解，也就是说，第 1 期杜立智等: P 与 NP 问题研究39只要可满足性问题具有多项式时间算法，则所有 NP 问题都具有多项式时间算法。具有这样特性的 NP 问题，称为 NP 完全问题。可满足性问题是人类发现的第一个 NP 完全问题。当然，以后若要寻找新的 NP 完全问题，就不需要再像库克那样，证明所有 NP 问题都可在多项式内转化到该问题，这样的证明是非常困难的。你只要证明任何一个已知的 NP 完全问题，能在多项式内转化到你所论及的问题就足够了。因为，不难理解，多项式转化具有传递性。从而，自

17、库克以后，不断地有 NP 完全问题被发6现 ，迄今已有四千多个 NP 完全问题被发现，这四千多个 NP 完全问题构成了一个庞大的 NP 完全树，树的根节点是库克的可满足性问题。当然若你能另起炉灶，不利用已知的 NP 完全问题，而是独立地证明一个新的 NP 完全问题，那你就创造了一棵新的 NP 完全树，所有这些 NP 完全树就会构成一个 NP 森林了。总之，面对目前的这四千多个 NP 完全问题，你只要证明其中任何一个问题具有多项式时间算法，就意味着你证明了 P = NP。反之，你只要证明这四千多个 NP 完全问题( 普通 NP 问题也行) 当中的任何一个是指数型问题，则意味着你证明了 P = !

18、 NP。无论哪一种情况，均意味着你破解了位列七大世界难题之首的那个高不可攀的问题，请注意，这是顶级的世界难题，切切不要以为仅凭简单的文字概念倒腾，或简单的思路就能解决。若是你认为你用了简单的思路或概念倒腾就解决了此问题的话，那么几乎可以绝对肯定，你的解答不仅是错误的，而且是荒唐荒谬的。3 种种错误的认识和不严谨的倾向分析最常见的一种错误认识和说法是，某问题是 NP 问题，因而不易求解，在大量的科研论文甚至某些算法教科书上都可以看到这样的说法。如前所述，所有 P 类问题，哪怕是最简单的 P 问题，同时也是 NP，所以，说只要是 NP 问题就难解无疑是错误的。正确的说法应该是，NP 难或 NP 完

19、全问题难解，因为迄今还没有一个这样的问题找到了多项式时间算法。关于 NP 难和 NP 完全的概念亦有很多误解。对于某个问题，若任何一个 NP 问题都可在多项式时间内按多项式的规模转化为对该问题的求解，则称该问题为 NP 难。显然，若任何一个 NP 难问题有多项式时间算法，则所有NP 问题具有多项式时间算法。而 NP 完全问题则是:既是 NP 难同时又属于 NP 的问题。另一种常见的误解就是，既然 P 和 NP 问题位列世界七大数学难题之首，那解决这个问题的人肯定必须是专业数学人才，需要高深的数学背景。国内一些权威期刊、权威科研学术机构的掌控者们，也有不少持这种认识。不难想象，在这种情况下，这样

20、的误解会导致什么。在此笔者谈几点关于这一问题的看法:1) NP 属计算机算法，算法问题的核心是复杂的思路，而不是数学理论和公式。2) 看看古今一些著名的算法，如: 最短路径，最小耗费生成树，装箱，旅行商问题等等，哪一个需要高深的数学理论?3) 甚至伟大的史蒂文库克关于 NP 完全的那个超难的开创性证明，也不包含高深的数学理论。4) 迄今已发现了四千多个 NP 完全问题，每一个发现都是一道艰难的证明题，其中没有一个需要高深的数学理论。5) 研究计算机算法，需要的是三种思维能力，即思维的多样性、巧妙性和深入性。其中，多样性体现的是想象能力，巧妙性是一种创造性思维，一种天分，而深入性则是深深地沿一条

21、思维脉络进行下去的能力。除了直接涉及到的相关数学外，一般不需要高深的数学理论。一种似是而非的观点是，P 和 NP 的关系不能一概而论，必须视环境范围而定。在确定性图灵机下，P 与 NP 是不等的，在非确定性图灵机下，P 与 NP 则相等。这显然是没有真正理解什么是 P 和 NP。P 和 NP 的定义非常明确，P 是可用多项式时间求解的问题，NP 是可用多项式时间验证其解答的问题，这个多项式明确是指在串行下也就是确定性图灵机下的多项式，当然，NP 也可以说是在非确定性图灵机下可用多项式时间求解的问题，NP 的这两个定义是等价的。根本不存在不同范围下的不同定义。退一步说，就算按这个理解，又如何能判

22、定在确定性图灵机下，P 和 NP 就不等呢?这样的论文能在国内影响力不低的科技期刊上读到，见参考文献7 9，可见这些期刊的编辑和相关的审稿专家需要加强这方面的正确认识。当然，这几篇论文除了这个概念错误外，同时也包含了一些原创性思想和闪光点。目前大多数本领域的知名权威倾向于认为，NP 不等于 P，例如 NP 完全问题的发明者史蒂文库克就持此看法。可以绝对肯定的是，权威们对于这一看法拿不出任何有力的根据，但此看法似乎已被大多数人默认，因而各种学术论文往往一谈到 NP 尤其是 NPC，就直截了当地声明，那不可能有多项式时间算法。这样的默认无疑是有害的。例如，ACM 一著名期刊主编 Lance For

23、tnow 写了一10篇 P vs NP 综述的论文 ，文中他认为: 1) no of us 真正懂得 NP; 2) NP 不大可能等于 P( unlikely) ; 3) 人类在短期内不可能解决该问题( unlikely) 。为了说明 NP40计算机技术与发展第 23 卷不大可能等于 P，他描绘了在 NP 等于 P 的前提下，会出现一个非常美妙的世界: 所有并行问题均可在多项式时间内得到解决，所有工序问题、优化问题、互联网路径、组网问题等等，都能迅速得到最优方案，甚至所有数学难题的解决亦能迅速在多项式时间内完成，因为解决任何数学难题实际上就是一个并行、多分支、呈指数型展开的过程，正确的通道也许

24、只有一个，此实际上就是 NP 问题。所以他认为，假使谁证明了 NP = P，则意味着七大世界难题他都解决了。他就差没说，如果谁证明了 NP = P，那谁就能掌控整个宇宙，因为包含人类智能活动的宇宙演化，理论上也可看做是一个多分支、不断并行展开的过程，我们此时所处的现实世界只是其中的一个分支，或只是其演化发展的一种可能性而已。尽管 Lance Fortnow 先生极具权威( 国际著名期刊的主编) ，但他的如此论述逻辑上显然是站不住脚的。甚至他自己在文中也承认: 即使证明了 NP = P，也不意味着你就能得到任意 NP 问题的有效的多项式时间算法。这里笔者将他的看法稍稍改一下: 假使人类拥有不受限

25、的非确定性图灵机，那他所描绘的那个美妙世界的确能出现。拥有不受限的非确定性图灵机意味着什么? 意味着你拥有无数劳动力，他们沿不同分支同时不交叉不重叠地按你的意图为你工作。试想，假使你拥有无数数学家，他们沿所有可能的方向( 分支) 同时并行地去攻一数学难题，有什么数学难题会不迅速被攻克? 然而，NP = P 与拥有不受限的非确定性图灵机并不等价。从逻辑上可以判断，人类永远不可能制造出不受限的非确定性图灵机。现在笔者想列举一下历史上曾经的权威看法后来的命运。这样的例子多不胜数，仅简列几例: 3，4 次方程的求根公式出来后，权威看法是，5 次，6 次乃至 N 次方程的求根公式将源源不断地出现，然而，

26、天才的伽罗华、阿贝尔却证明，高于 4 次的方程不可能有通用的求根公式; 素数定理在用高等数学证明后，权威看法是，其不可能在初等数学范围内得证，爱多士等人偏偏就用初等数学证明了它; 权威们曾经普遍认为宇称守恒，杨振宁李政道就是要证明宇称不守恒; 不变量定理曾被权威们判断无法用初等数学求解，希尔伯特就用初等数学证明了它; 曾经认为，数是完整完美的，所有的数均可用分数表示，毕达哥拉斯的那位学生轻易摧毁了这个权威论断，等等。怀尔斯证明了费尔马大定理，他本人断言，费尔马大不可能在初等数学范围内得证;陈景润用筛法证明了 1 + 2，有权威断言，陈已将筛法用到了极限，因而 1 + 1 不可能用筛法完成。从历

27、史上看，这样的断言几乎没有价值。科学的发展，有时需要打破权威们的思想禁锢。4 研究发展趋势展望研究 NP 问题，有两个方面的含义，一个是研究 NP 问题本身的算法，即如何快速地计算 NP 问题，另一个就是研究 NP 与 P 的关系。关于 NP 的计算问题，大家知道，计算机硬件是按照摩尔定律在飞速发展的，目前我国的天河计算机已达到每秒能计算一千万亿次的速度。因而有人认为，随着计算机计算速度的飞跃发展，就算没有计算理论上的突破，成规模的 NP 问题的计算也很快能实现。这当然是一种错误的认识。许多 NP 问题目前有效算法的时间复杂度是形如 2 的 n 次方这样的指数型。在这种情况下，即使 n 的规模

28、仅仅只是达到了 100 ，2 的 100 次方是 100 万亿亿亿，用天河计算机需要一千万亿秒，那是个什么概念，几千万年! 并且，就算最快的计算机能达到计算 2 的 100 次方，n再扩大一倍就是 200 ，此时计算速度需要提高多少倍呢?100 万亿亿亿倍，这样的计算速度，至少目前看来，对人类是遥不可及的。NP 问题有一个显著特点就是能并行计算，这个与现今已明确的指数型问题不同，于是人们想到了并行计算机。关于这方面的研究，有 DNA 计算机，有量子计算机等，均认为这样的计算机能并行计算。然而，这样的研究已进行了几十年，投入了大量的人力资金，目前的情况依然是，其实际计算能力甚至连人的手工计算都不

29、如。用于有价值的实战即使不是毫无希望的，10也是遥不可及的 。所以要想解决 NP 问题，还得靠计算理论上的突破。对于难解的 NP 问题，理论上不能或很难找到多项式时间算法，多年来普遍采取的研究方法是，寻找其11近似算法或概率算法 ，使其接近最终解或以较高的概率正确计算出最终解。这方面，针对不同的问题，不断地有一些进展。最显著的例子有，关于质数的判定，原来一直倾向于认为，该问题不太可能有多项式时间算法，只能有指数解。但前几年两位印度科学家发现了一种算法，能在多项式时间内解决该问题，从而引起了轰动。当然，从根本上解决 NP 问题的途径是，或者证明 NP 等于 P，从而从理论上找到 NP 问题的多项

30、式时间算法; 或者证明 NP 不等于 P，从而，某些 NP 问题永远也不可能有多项式时间算法，以免白费时间精力。如前所述，这两个集合的关系只有两种可能性，要么相等，要么不等。若要证明 P 等于 NP，穷举 NP 里面的所有元素，证明里面的每一元素同时也属于 P，这样的方法肯定是不可取的。1971 年，伟大的史蒂文 库克发现并证明了第一第 1 期杜立智等: P 与 NP 问题研究41个 NP 完全问题。自那以后，人类已找到了数千个这样的问题。NP 完全问题的意义在于，任何 NP 问题都可以在多项式时间内按多项式的规模转化为对任一NP 完全问题的求解。从而，若某一 NP 完全问题具有多项式时间算法

31、，则意味着所有 NP 问题都具有多项式时间算法。因此，若能证明任一 NP 完全问题具有多项式时间算法，则等同于证明了 P 等于 NP。显然，这是证明 P 等于 NP 的根本途径。若试图绕过这一途径，幻想有更简单更“巧妙”的方法，或幻想仅对概念进行文字上的倒腾就能得出结果，那只能是徒劳的 ( 许多错误的“证明”都是这样干的) 。第二种可能就是 P 不等于 NP。若要证明 P 不等于 NP，你必须在 NP 里面找到一个元素，证明该元素不属于 P，或者你没有具体找出这样的元素，但从理论上证明了必然有这样的元素存在。同样，幻想绕过这样的途径，通过倒腾概念来得出结论，只能是荒谬的。事实上，许多人由于没有

32、理解 P 和 NP 的实质，仅仅只是背了一下关于确定性和非确定性图灵机、语言、空间等概念，又没有理解透，将概念进行无谓的倒腾，以为仅凭这些概念的文字表述所指的范畴，就能得出 P 不等于 NP 的结论，这无疑是研究该问题的一种歧途。当然，除非你用来倒腾的概念原理本身已经做过这样的工作，但从目前来看，应该不存在这样的概念原理。在这方面最轰动的例子要数印度人惠普实验室研究员 Vinay Deolalikar 了。它于 2010 年声称已经证明 “P! = NP”，在网上公开了论文草稿。并私下将 100 来页的论文草稿发给了相关研究领域的若干主要研究者审查。早在他的论文刚一公布，笔者就做出了如下评论:

33、P 是否等于 NP，属超级难题，一直未解。不少人声称已解决该难题，但未被认可。如今的 Vinay Deola-likar 声称已经证明“P! = NP”，前景如何? 关于 P 对NP 问题，目前有三种观点: 1，认为 P!= NP，2，认为 P= = NP，3，认为无法确定，甚至人类永远无法确定。第一类是主流。先谈他的优势: 英文表达很溜，英文论文的写作水平，结构及表达方式一流，因而很吸人眼球; 拥有惠普实验室的研究员的头衔，之前已有不少带原创价值的成果; 跨多学科，知识广泛，idea 新颖; 论文洋洋万言，长篇大论，符合此类论文的特点; 结论符合大多数主流权威专家的看法。再谈可能的问题: 简

34、单的逻辑是，证明越单一，越简洁，越易于被确定，而越复杂越“倒腾”，越易将人搞糊涂，包括将他自己搞糊涂。他采取的是跨多学科，将多种不同源的概念原理连接起来，综合得出证明结论的方式，方法新颖，具有创意，之前从未有人想到过，因而易引起关注和敬畏。然而，恰恰是这些可能使他陷入深渊:1 因跨多学科，他自己对其他学科相应的概念原理理解的深度和准确度的问题;2 多学科概念原理连接时，概念原理在内涵外延上衔接会否出现缝隙问题;3 他用的是抽象的理论推导，抽象的概念原理堆砌，将一个领域的概念原理应用到另一个领域时，在对概念原理的应用适当性方面的理解会否出现根本性偏差的问题，若是，则从根本上动摇了整个证明。后来的

35、结果印证了笔者当他的论文刚公布时的评论，因跨多学科，他自己对其他学科相应的概念原理理解的深度和准确度出了问题，从而导致致命错误。也就是说，他应用了非他自己所专长的领域里的原理，而在这种应用中，他的某些理解被该领域的顶级专家判定为: 致命错误。他错误的根源在于: 如前所述，若要证明 P 不等于NP，你必须在 NP 里面找到一个元素，证明该元素不属于 P，或者你没有具体找出这样的元素，但从理论上证明了必然有这样的元素存在。幻想绕过这样的途径，通过倒腾概念来得出结论，只能是荒谬的。当然，除非你用来倒腾的概念原理本身已经做过这样的工作，但据专家认为，他所依赖的概念原理并没有做这样的工作，从而，他的证明

36、从根本上是不成立的。有一种方法被广泛应用于研究 NP 问题，用 AND，OR，NOT 等逻辑门组成的电路，门的个数为多项式，来解决某个 NP 问题。若能证明某个 NP 不可能由这样的逻辑电路来解决，则就证明了 NP 不等于 P。多年的尝试表明，该方法并不能为解决 NP 问题带来什么便利。还有一种方法也一度被尝试用来解决 P 与 NP 的关系问题，那就是对角线法，康托尔正是使用该方法证明: 实数集大于自然数集。后来图灵又用它来证明停机问题的不可解。然而，该方法在逻辑上存在着重大争议或缺陷，不可滥用。并且，研究表明，该方法也不适合于研究 NP 和 P 的关系。此外，由于互联网的发展，广泛利用互联网

37、资源进12，13行分布式计算包括蚁群算法的运用，以及目前发14，15展火热的所谓云计算 ，均是计算 NP 问题可采用的有效手段，它们都是利用了 NP 问题的并行性特点。总之，除了前述的两种根本途径外，解决 NP 问题没有便利的捷径。目前学术界普遍认为，彻底解决 P和 NP 的关系问题还有遥远的距离。笔者希望这一预言能被迅速打破。若是 NP 真的等于 P 的话，那么，迅速打破上述预言的可能性时时存在，因为现在已经发现了四千多个 NP 完全问题，只要对其中任意一个找42计算机技术与发展第 23 卷到了多项式时间算法，也就证明了 NP 等于 P。而从历史上看，某个高难度的问题突然被人发现具有美妙的算

38、法的事例是时有发生的。最典型的就是那两位印度科学家找到了关于质数判定的多项式时间算法，而这样的算法在他们之前一直被认为是不太可能的。+Ms l : McGraw Hill，19985Cook S A The complexity of theorem proving procedures C/ /Proceedings of Third Annual ACM Symposium on The-ory of Computing New York: Association for Computing Ma-chinery，1971: 151 1586 Karp R M Reducibility a

39、mong combinatorial problemsM/ / Complexity of Computer Computations New York: Plenum5 结束语NP 问题是理论计算机领域最重要的问题之一，其相关概念原理相当复杂而难以理解，不少这方面的研究者包括一些基金及论文评审专家、科技期刊的掌控者，对其中一些重要概念的理解都很模糊。文中用通俗的语言，从多个方面论述了与 NP 问题相关的最核心概念，分析了不同角度的研究方法和研究途径，包括列举分析了一些失败或错误的研究方法以及对基本概念最常见的一些错误理解，同时对该问题的研究前景进行了分析预判，可供相关人员参考。参考文献:1A

40、rora S，Barak B Complexity Theory: A Modern ApproachM Cambridge: Cambridge University Press，20092Aaronson S Is P versus NP formally independent? J Bulle-tin of the European Association for Theoretical Computer Sci-ence，2003，81: 109 1363杜丁柱，葛可一，王洁 计算复杂性导引M 北京: 高等教育出版社，2002: 35 574Sahni S Data Structur

41、es，Algorithms and Applications in C +Press，1972: 85 1047杨正瓴 密码学与非确定型图灵机J 中国电子科学研究院学报，2008，3( 6) : 558 5628杨正瓴 第二类计算机构想J 中国电子科学研究院学报，2011，6( 4) : 368 3749Yang Zhengling A non canonical example to support that P is not equal to NPJ Transactions of Tianjin University，2011，17( 6) : 446 44910 Fortnow L The Status of the P Versus NP ProblemJ Com-munications of the ACM，2010，52( 9) : 78 8611 Posa L Hamiltonian circuits in random graphsJ Discrete Math ，1976，14( 4) : 359 36412 俞 慧，吴 巍，黄 潇，等 基于改进的蚁群算法的组播路由