从中国象棋到NP完全问题

1、从中国象棋到NP完全问题【摘要】 数学发展到21世纪，便和计算机的发展有了不解之缘。文章从古老的象棋谈起，围绕计算机的的灵魂算法，也是数学最古老的本质论题，谈到了数学机械化的可能性。通过对可计算理论和复杂性理论的阐述，引出“千禧年数学难题”中最重要的问题之一NP完全问题的基本理论和研究思想，在加深对NP完全性的理解之上，探讨我们所生活的这个世界的本质所在，我们所研究的数学问题的本质所在以及它的终极结论。全文涉及到很多基本概念，主要内容是围绕算法谈论NP完全问题的来龙去脉，从思想上深入理解这一千年难题的根本所指。【关键字】 算法 机械证明 数学千年难题 计算复杂性 NP完全性 终极理论0. 引言

2、这个世界的本质是什么？这是一个无人能回答的问题，也是一个值得人们永无止尽地去探求的问题。也许借助于“数学”这个人类至今所发明的最强有力的工具，我们会离答案更近一点。从万物的起源谈起，人类总不忘尝试着去复原那远古混沌的图景，也渴望着发现终极理论来诠释我们所在的宇宙。数学先于人类诞生，毋庸置疑！数学就是那万物得以有序运行的机制所在，数学就是我们所渴求的终极理论的美妙琴弦！霍金借助于数学工具，写出时间简史，增进了我们认识宇宙的深度；菜场上的老大娘默默念叨着菜价，为生计精打细算；华尔街的金融师做着大量的分析和计算，预测出全球金融市场的风起云涌；活跃在21世纪IT舞台的精英们也在尝试着把人类的实际需求转

3、化成一个个的程序，交给计算机去处理由此可见，数学的深入发展与人类的命运息息相关，不管是对个人还是群体。纵观数学辉煌的发展史，在各类简单的或是复杂的数学问题中，有没有共通的东西呢？有！那就是算法！你会惊讶地发现，算法似乎就是数学的本质！任何在数学上已解决了的问题都可以交给算法去处理，任何运行的机制和运动的物体都可以用算法来描述！于是我们就有了这样一个疑问：是否任何问题的解决都可以归结为寻求到相应的算法？然而，情况并不乐观，仍然存在着大量的不可计算的问题，也就是不能用算法来描述的问题让人们困惑不已。事实上，我们现在所掌握的数学并不是完美的。就像我们建立的现代科学体系，数学也只是对客观世界的近似刻画

4、，是人类为获得外界信息所发明的一个有力工具。类似于语言，数学使得先辈们的生活经验得以记录下来，数学符号使得人们精确思维有了载体。数学的不完美性和持续发展性也能够从数学史上的三大悖论窥得，而每一个难题的解决则是人类思维升华、大脑进化的必然过程！数学需要深刻的思考，而正是这深入的思考促进了社会的发展。当不可思议的悖论发生的时候，那必然是我们的工具出了漏洞，在苦苦思索之后，我们的蒙昧与无知得到洗涤，我们对世界的认识也更加深入了。本文较系统地阐述了算法的一个高级话题NP难问题的其来龙去脉。文章从古老的中国象棋谈起，深入认识算法的本质，并由此延伸到数学的机械化。在对当今世界数学七大难题核心思想的了解下，

5、进一步探析了计算复杂性的理论。文章最后围绕NP难问题，尝试着使其在思维上明朗化，以摆脱框框条条的束缚，站在哲学的高度来审视数学的本质所在，从而提高我们认识世界的广度和深度。1. 美妙的算法1997年5月，深蓝第二次次挑战国际象棋世界冠军卡斯巴罗夫，比赛在5月11日结束，最终深蓝电脑以3.5：2.5击败卡斯巴罗夫，成为首个在标准比赛时限内击败国际象棋世界冠军的电脑系统。深蓝战胜人脑的根本所在在于它使用了更加优良的算法，而国际象棋大师的脑海中也储存了大量的棋谱和固有的逻辑推理。中国古代象棋也是一种基于推理的益智游戏，它是对古代战争的抽象模拟，对提高战将们的逻辑推理和思维的严密性很有帮助。弈棋高手大

6、都熟悉很多棋谱（如下图所示），而那一张张棋谱实际上就是某一算法确定的一步，谁的算法更优，谁就能赢得棋局。 图1-0 中国象棋 图1-1 棋谱1.1 算法的定义那么到底什么是算法呢？算法可以理解为有基本运算及规定的运算顺序所构成的完整的解题步骤。或者看成按照要求设计好的有限的确切的计算序列，并且这样的步骤和序列可以解决一类问题。定义1.1 算法是求解问题类的、机械的、统一的方法，它由有限多个步骤组成，对于问题类中的每个给定的具体问题，机械地执行这些步骤就可以得到问题的解答。正是由于算法的这种特性，才使得计算不仅可以由人，而且可以由计算机来完成。这也是深蓝得以战胜人脑的依据所在。用计算机解决问题的

7、过程可以分成三个阶段：分析问题、设计算法和实现算法。1.2 算法的历史中国古代的筹算口诀与珠算口诀及其执行规则就是算法的雏形，这里，所解决的问题类是算术运算。古希腊数学家欧几里得在公元前3世纪就提出了一个算法，来寻求两个正整数的最大公约数，这就是有名的欧几里得算法，亦称辗转相除法。中国早已有“算术”、“算法”等词汇，但是它们的含义是指当时的全部数学知识和计算技能，与现代算法的含义不尽相同。英文algorithm(算法)一词也经历了一个演变过程，最初的拼法为algorism或algoritmi，原意为用阿拉伯数字进行计算的过程。这个词源于公元 9世纪波斯数字家阿尔·花拉子米的名字的最后

8、一部分。在古代，计算通常是指数值计算。现代计算已经远远地突破了数值计算的范围，包括大量的非数值计算，例如检索、表格处理、判断、决策、形式逻辑演绎等。欧几里得算法被人们认为是史上第一个算法。第一次编写程序是Ada Byron于1842年为巴贝奇分析机编写求解伯努利方程的程序，因此Ada Byron被大多数人认为是世界上第一位程序员。因为查尔斯·巴贝奇(Charles Babbage)未能完成他的巴贝奇分析机，这个算法未能在巴贝奇分析机上执行。因为“well-defined procedure”缺少数学上精确的定义，19世纪和20世纪早期的数学家、逻辑学家在定义算法上出现了困难。20世纪

9、的英国数学家图灵提出了著名的图灵论题，并提出一种假想的计算机的抽象模型，这个模型被称为图灵机。图灵机的出现解决了算法定义的难题，图灵的思想对算法的发展起到了重要作用的。在20世纪以前，人们普遍地认为，所有的问题类都是有算法的。20世纪初，数字家们发现有的问题类是不存在算法的，遂开始进行可行性研究。在这一研究中，现代算法的概念逐步明确起来。30年代，数字家们提出了递归函数、图灵机等计算模型，并提出了丘奇图灵论题，这才有可能把算法概念形式化。按照丘奇-图灵论题，任意一个算法都可以用一个图灵机来实现，反之，任意一个图灵机都表示一个算法。按照上述理解，算法是由有限多个步骤组成的，它有下述两个基本特征：

10、每个步骤都明确地规定要执行何种操作；每个步骤都可以被人或机器在有限的时间内完成。人们对于算法还有另一种不同的理解，它要求算法除了上述两个基本特征外，还要具有第三个基本特征：虽然有些步骤可能被反复执行多次，但是在执行有限多次之后，就一定能够得到问题的解答。也就是说，一个处处停机（即对任意输入都停机）的图灵机才表示一个算法，而每个算法都可以被一个处处停机的图灵机来实现1.3 算法分类算法可大致分为基本算法、数据结构的算法、数论与代数算法、计算几何的算法、图论的算法、动态规划以及数值分析、加密算法、排序算法、检索算法、随机化算法、并行算法等。算法还可以宏泛的分为三类：有限的，确定性算法 这类算法在有

11、限的一段时间内终止。他们可能要花很长时间来执行指定的任务，但仍将在一定的时间内终止。这类算法得出的结果常取决于输入值。有限的，非确定算法 这类算法在有限的时间内终止。然而，对于一个（或一些）给定的数值，算法的结果并不是唯一的或确定的。无限的算法 是那些由于没有定义终止定义条件，或定义的条件无法由输入的数据满足而不终止运行的算法。通常，无限算法的产生是由于未能确定的定义终止条件。1.4 算法的特征一个算法应该具有以下五个方面的重要特征：输入 一个算法有零个或多个输入，以刻画运算对象的初始情况。例如，在欧几里得算法中，有两个输入，即m和n。确定性 算法的每一个步骤必须要确切地定义。即算法中所有有待

12、执行的动作必须严格而不含混地进行规定，不能有歧义性。例如，欧几里得算法中，步骤1中明确规定”以m除以n，而不能有类似以m除n以或n除以m这类有两种可能做法的规定。有穷性 一个算法在执行有穷步滞后必须结束。也就是说，一个算法，它所包含的计算步骤是有限的。例如，在欧几里得算法中，m和n均为正整数，在步骤1之后，r必小于n，若r不等于0，下一次进行步骤1时，n的值已经减小，而正整数的递降序列最后必然要终止。因此，无论给定m和n的原始值有多大，步骤1的执行都是有穷次。输出 算法有一个或多个的输出，即与输入有某个特定关系的量，简单地说就是算法的最终结果。例如，在欧几里得算法中只有一个输出，即步骤2中的n

13、。可行性 算法中有待执行的运算和操作必须是相当基本的，换言之，他们都是能够精确地进行的，算法执行者甚至不需要掌握算法的含义即可根据该算法的每一步骤要求进行操作，并最终得出正确的结果。1.5 算法的基本方法下面简单介绍算法的一些基本方法，而基于这些方法的分治策略、贪心策略、动态规划策略、分支限界法、回溯法等则是五种通用的算法设计技术。递推法 递推法是利用问题本身所具有的一种递推关系求问题解的一种方法。它把问题分成若干步，找出相邻几步的关系，从而达到目的。递归法 递归指的是一个过程：函数不断引用自身，直到引用的对象已知。穷举搜索法 穷举搜索法是对可能是解的众多候选解按某种顺序进行逐一枚举和检验，并

14、从中找出那些符合要求的候选解作为问题的解。贪婪法 贪婪法是一种不追求最优解，只希望得到较为满意解的方法。贪婪法一般可以快速得到满意的解，因为它省去了为找最优解要穷尽所有可能而必须耗费的大量时间。贪婪法常以当前情况为基础作最优选择，而不考虑各种可能的整体情况，所以贪婪法不要回溯。分治法 分治法是把一个复杂的问题分成两个或更多的相同或相似的子问题，再把子问题分成更小的子问题直到最后子问题可以简单的直接求解，原问题的解即子问题的解的合并。动态规划法 动态规划是一种在数学和计算机科学中使用的，用于求解包含重叠子问题的最优化问题的方法。其基本思想是，将原问题分解为相似的子问题，在求解的过程中通过子问题的

15、解求出原问题的解。动态规划的思想是多种算法的基础，被广泛应用于计算机科学和工程领域。 迭代法 迭代法是数值分析中通过从一个初始估计出发寻找一系列近似解来解决问题（一般是解方程或者方程组）的过程，为实现这一过程所使用的方法统称为迭代法。分支界限法 与贪婪算法一样，这种方法也是用来为组合优化问题设计求解算法的，所不同的是它在问题的整个可能解空间搜索，所设计出来的算法虽其时间复杂度比贪婪算法高，但它的优点是与穷举法类似，都能保证求出问题的最佳解，而且这种方法不是盲目的穷举搜索，而是在搜索过程中通过限界，可以中途停止对某些不可能得到最优解的子空间进一步搜索（类似于人工智能中的剪枝），故它比穷举法效率更

16、高。1.6 典型算法举例算法可以用自然语言描述。自然语言是人们日常所用的语言，如汉语、英语、德语等。使用这些语言不用专门训练，所描述的算法也通俗易懂。算法也可以用流程图描述。在数学课程里，我们学习了用程序框图来描述算法。在程序框图中流程图是描述算法的常用工具，即由一些图形符号来表示算法。算法还可以用伪代码描述。伪代码是用介于自然语言和计算机语言之间的文字和符号来描述算法的工具。它不用图形符号，因此，书写方便、格式紧凑，易于理解，便于向计算机程序设计语言过度。公元前250年古希腊的数学家埃拉托塞尼提出一种筛法来求素数，下面我们用自然语言来描述该算法：Step1 要得到不大于某个自然数N的所有素数

17、，只要在2N中将不大于N的素数的倍数全部划去即可。Step2 将上面的内容等价转换：“如果N是合数，则它有一个因子d满足1<dN”。Step3 再将Step2的内容等价转换：“若自然数N不能被不大于N的任何素数整除，则N是一个素数”。Step4 这句话的汉字可以等价转换成为用英文字母表达的公式： N = p1m1+a1 = p2m2+a 2= =pkmk+ak. (1) 其中p1，p2， ，pk表示顺序素数2，3，5， ，a0。即N不能是2m+0，3m+0，5m+0， ，pkm+0形。若N<P（k+1）的平方，则N是一个素数。Step5 可以把(1)等价转换成为用同余式组表示： N

18、a1(modp1)，Na2(modp2)， ，Nak(modpk). (2)例1.6.1 29不能够被根号29以下的任何素数2，3，5整除，29=2×14+1=3×9+2=5×5+4。291(mod2)，292(mod3)，294(mod5)。29小于7的平方49，所以29是一个素数。由于(2)的模p1，p2，pk 两两互素，根据孙子定理(中国剩余定理）知，(2)在p1pk范围内有唯一解。例1.6.2 k=1时，N=2m+1，解得N=3，5，7。求得了（3，32）区间的全部素数。k=2时，N=2m1+1=3m2+1，解得N=7，13，19； N=2m1+1=3m2

19、+2，解得N=5，11，17，23。求得了（5，52）区间的全部素数。k=3时，N=2m1+1=3m2+1=(5m3+1/5m3+2/5m3+3/5m3+4)，解得N=13，19，31，37，43。N=2m1+1=3m2+2=(5m3+1/5m3+2/5m3+3/5m3+4)，解得N=11，17，23，29，41，47。求得了（7，72）区间的全部素数。仿此下去，可以求得任意大的数以内的全部素数。2. 数学机械化数学问题的机械化，就是要求在运算或证明过程中，每前进一步之后，都有一个确定的、必须选择的下一步，这样沿着一条有规律的、刻板的道路，一直达到结论。即所谓的机械化就是刻板化和规格化。这一起

20、源于中国古代传统数学，由于计算机的出现而呈现旺盛生命力的数学机械化思想在数学研究上已经发挥出它的巨大威力，并且对当今数学及数学教学产生了具大的影响。计算机科学被认为是算法的科学。以算法为核心的机械化思想，既传统又前瞻，将为信息时代数学科学的创新发挥重大作用。“计算机证明数学问题”是由吴文俊提出的，华人美籍数学家王浩也是最初的研究人员之一。它是极为神奇的超级工程数学，有可能引发工程技术的革命和某些基础数学的革命。数学机械化研究，是在初等几何定理的机器证明研究方面取得突破的。公理化体系的几何定理证明非常灵活。以中学课程中的几何为例，个定理的证明，往往要经过冥思苦想，奇巧构思，无章可循地填加辅助线，

21、迂回曲折地给出证明。如何利用计算机进行自动推理，特别是进行几何定理的自动证明，是学术界长期研究的课题。所谓定理的机械化证明，就是对一类定理（这类定理可能成千上万）提供一种统一的方法，使得该类定理中每个定理，都可依此方法给出证明。在证明过程中，每前进一步，都有章可循地确定下一步该做什么和如何做。从“一理一证”到“类一证”，是数学的认识和实践的飞跃。吴先生创立了初等几何（泛指不具有微分运算的几何，如欧氏几何、非欧几何、仿射几何、投影几何、代数几何等等）定理证明的机械化方法，国际上称“吴方法”，首次实现了高效的几何定理的机器证明。“吴方法”也可用于几何定理的自动发现和未知关系的自动推导。吴文俊先生的

22、开创性成果，打破了国际自动推理界在几何定理自动证明研究中长期徘徊不前的局面，也使我国在这一领域处于领先地位。数学是研究数量关系和形体性质的科学。“数”与“形”在现实世界中无处不在，因此，数学科学是自然科学的基础，也是高新技术的基础，甚至是工程建设的基础，这已是人们的共识。数学科学的好处是，可以化难为易，把奥妙变为常识，为各类问题的解决提供框架。吴文俊先生强调：“数学机械化方法的应用，是数学机械化研究的生命线”。他本人的研究工作己涉及许多应用领域，如线性控制系统、机构综合设计、平面星体运行的中心构形、化学反应方程的平衡、代数曲面的光滑拼接、从开普勒定律自动推出牛顿定律、全局优化求解等等。在他的指

23、导和带动下，数学机械化方法己在一些交叉研究领域获得初步应用，如理论物理、计算机科学、信息科学、自动推理、工程几何、机械机构学等等。数学机械化研究不断开拓更多的应用方面。吴文俊先生说过，从事数学研究，要有良好的思维方式，在思想观念上要有所突破。许多事例表明，些数学分支正是由于踏上了机械化的道路而获得了蓬勃的发展，使之成为重要的研究方向，甚至成为数学的主流。这是因为，抽象的数学概念和结论，往往是难于掌握和运用的。当把抽象的概念变成具体可算的（算法经常用公式表达），既有定性的结论又有定量的计算，数学理论才臻于完善，易于接受和适宜应用。运用机械化思想考察数学，将会发现数学的不同侧面，建立新的模式，活跃

24、和启迪数学家的思维，从而产生大量的原始创新。证定理和解方程，大体上涵盖了数学活动的主要内容。在机器证定理和机器解方程两个方面，吴文俊先生在理论和方法上都做出了原创性的贡献。机器定理证明 机器定理证明就是把人证明数学定理和日常生活中的演绎推理变成一系列能在计算机上自动实现的符号演算的过程和技术，又称自动定理证明和自动演绎。机器定理证明是人工智能的重要研究领域，它的成果可应用于问题求解、自然语言理解、程序验证和自动程序设计等方面。数学定理证明的过程尽管每一步都很严格有据，但决定采取什么样的证明步骤，却依赖于经验、直觉、想象力和洞察力，需要人的智能。因此，数学定理的机器证明和其他类型的问题求解，就成

25、为人工智能研究的起点。早在17世纪中叶，莱布尼兹就提出过用机器实现定理证明的思想。19世纪后期G.弗雷格的“思想语言”的形式系统，即后来的谓词演算，奠定了符号逻辑的基础，为自动演绎推理提供了必要的理论工具。20世纪50年代，由于数理逻辑的发展，特别是电子计算机的产生和应用，机器定理证明才变为现实。A.纽厄尔和H.A.西蒙首先用探试法实现了用以证明命题逻辑中重言式的逻辑理论家系统。L.T.后来开始探讨通用的机器定理证明的方法，归结原理是其中突出的例子。归结原理和非归结定理证明 一阶谓词逻辑的恒真性问题是不可解的，即不存在能判定一阶逻辑中任意合式公式是不是永真式的算法，但是这个问题又是部分可解的。

26、如果A是永真式，那么必有算法可以证明。许多一阶逻辑的证明算法都以J.厄尔布朗定理为基础，其中以1965年J.A.鲁宾逊提出的、对于一阶逻辑是完备的证明算法即归结原理最为著名。归结原理的提出，把机器定理证明的研究推向高潮。但归结原理不依赖于领域知识，不使用依赖问题领域的探试法，证明过程冗长，不能在合理的时间和计算机存储容量内证明较为复杂的数学定理，因此人们又提出非归结定理证明方法，后来又对以探试法为基础的问题求解技术发生兴趣。与此同时还出现了因否定归结原理进而否定所有自动演绎方法的倾向。但是人工智能所要解决的问题，其信息往往是不完全的，而且即使信息完全，要对有限的但为数众多的情形一一列举，实际上

27、也不可行，因而只有用演绎推理的方法。逻辑程序设计和日本以PROLOG为原型开发第五代计算机系统的核语言，进一步恢复了归结原理和自动演绎技术的地位。人工智能的历史表明，以认知心理学为基础的探试法和以逻辑为基础的自动演绎相辅相成，不可偏废。自动演绎与探试法等技术相结合而不用归结原理的定理证明技术，主要用于数学定理的机器证明。几何定理的机器证明 在数学定理机器证明中，有一类问题已有判定算法，如1951年W。斯米列夫给出的阿贝尔群判定算法，1951年A.塔斯基给出的初等几何和代数的判定算法，1960年王浩提出的命题逻辑判定算法和1976年以来吴文俊提出的初等几何和微分几何定理机器证明的理论和方法。非标

28、准逻辑中的自动演绎 以经典的一阶逻辑为基础的自动演绎技术比较成熟。为了适应人工智能中复杂的推理形式，需要研究高阶逻辑和非标准逻辑中的自动演绎技术并从实用角度将这类逻辑表示形式转换成等价的经典一阶逻辑的表示形式。逻辑程序设计 将一阶谓词演算的子集直接作为程序设计语言的技术和方法。PROLOG语言是初步实现逻辑程序设计基本思想的第一个语言，R.科瓦尔斯基则曾对HORN子句作了过程性解释，系统地阐明了逻辑程序设计的基本理论。3. 千年大奖问题20世纪是数学大发展的一个世纪。数学的许多重大难题得到完满解决，如费马大定理的证明，有限单群分类工作的完成等，从而使数学的基本理论得到空前发展。计算机的出现是2

29、0世纪数学发展的重大成就，同时极大推动了数学理论的深化和数学在社会和生产力第一线的直接应用。回首20世纪数学的发展，数学家们深切感谢20世纪最伟大的数学大师大卫·希尔伯特。希尔伯特在1900年8月8日于巴黎召开的第二届世界数学家大会上的著名演讲中提出了23个数学难题。希尔伯特问题在过去百年中激发数学家的智慧，指引数学前进的方向，其对数学发展的影响和推动是巨大的，无法估量的。效法希尔伯特，许多当代世界著名的数学家在过去几年中整理和提出新的数学难题，希冀为新世纪数学的发展指明方向。这些数学家知名度是高的，但他们的这项行动并没有引起世界数学界的共同关注。2000年初美国克雷数学研究所的科学

30、顾问委员会选定了七个“千年大奖问题”，克雷数学研究所的董事会决定建立七百万美元的大奖基金，每个“千年大奖问题”的解决都可获得百万美元的奖励。克雷数学研究所“千年大奖问题”的选定，其目的不是为了形成新世纪数学发展的新方向，而是集中在对数学发展具有中心意义、数学家们梦寐以求而期待解决的重大难题。2000年5月24日，千年数学会议在著名的法兰西学院举行。会上，98年费尔兹奖获得者伽沃斯以“数学的重要性”为题作了演讲，其后，塔特和阿啼亚公布和介绍了这七个“千年大奖问题”。克雷数学研究所还邀请有关研究领域的专家对每一个问题进行了较详细的阐述。克雷数学研究所对“千年大奖问题”的解决与获奖作了严格规定。每一

31、个“千年大奖问题”获得解决并不能立即得奖。任何解决答案必须在具有世界声誉的数学杂志上发表两年后且得到数学界的认可，才有可能由克雷数学研究所的科学顾问委员会审查决定是否值得获得百万美元大奖。“千年大奖问题”公布以来，在世界数学界产生了强烈反响。这些问题都是关于数学基本理论的，但这些问题的解决将对数学理论的发展和应用的深化产生巨大推动。认识和研究“千年大奖问题”已成为世界数学界的热点。不少国家的数学家正在组织联合攻关。可以预期，“千年大奖问题”将会改变新世纪数学发展的历史进程。这七个“千年大奖问题”分别是：NP完全问题、霍奇猜想、庞加莱猜想、黎曼假设、杨米尔斯理论、纳卫尔斯托可方程、BSD猜想。难

32、题一 P(Polynomial算法)问题对NP(Non-deterministic Polynomial算法)问题在一个周六的晚上，你参加了一个盛大的晚会。由于感到局促不安，你想知道这一大厅中是否有你已经认识的人。你的主人向你提议说，你一定认识那位正在甜点盘附近角落的女士罗丝。不费一秒钟，你就能向那里扫视，并且发现你的主人是正确的。然而，如果没有这样的暗示，你就必须环顾整个大厅，一个个地审视每一个人，看是否有你认识的人。生成问题的一个解通常比验证一个给定的解时间花费要多得多。这是这种一般现象的一个例子。与此类似的是，如果某人告诉你，数13，717，421可以写成两个较小的数的乘积，你可能不知道

33、是否应该相信他，但是如果他告诉你它可以因子分解为3607乘上3803，那么你就可以用一个袖珍计算器容易验证这是对的。不管我们编写程序是否灵巧，判定一个答案是可以很快利用内部知识来验证，还是没有这样的提示而需要花费大量时间来求解，被看作逻辑和计算机科学中最突出的问题之一。NP完全问题是不确定性图灵机在P时间内能解决的问题。整个计算机科学的大厦就建立在图灵机可计算理论和计算复杂性理论的基础上，一旦证明P=NP，将是计算机科学的一场决定性的突破，在软件工程实践中，将革命性的提高效率。从工业，农业，军事，医疗到生活，软件在它的各个应用域，都将是一个飞跃。P=NP吗? 这个问题是著名计算机科学家(198

34、2年图灵奖得主)斯蒂文·考克（Stephen·Cook）于1971年发现并提出的。难题二 霍奇(Hodge)猜想二十世纪的数学家们发现了研究复杂对象的形状的强有力的办法。基本想法是问在怎样的程度上，我们可以把给定对象的形状通过把维数不断增加的简单几何营造块粘合在一起来形成。这种技巧是变得如此有用，使得它可以用许多不同的方式来推广；最终导致一些强有力的工具的发明，使数学家在对他们研究中所遇到的形形色色的对象进行分类时取得巨大的进展。不幸的是，在这一推广中，程序的几何出发点变得模糊起来。在某种意义下，必须加上某些没有任何几何解释的部件。霍奇猜想断言，对于所谓射影代数簇这种特别完

35、美的空间类型来说，称作霍奇闭链的部件实际上是称作代数闭链的几何部件的(有理线性)组合。难题三 庞加莱(Poincare)猜想 如果我们伸缩围绕一个苹果表面的橡皮带，那么我们可以既不扯断它，也不让它离开表面，使它慢慢移动收缩为一个点。另一方面，如果我们想象同样的橡皮带以适当的方向被伸缩在一个轮胎面上，那么不扯断橡皮带或者轮胎面，是没有办法把它收缩到一点的。我们说，苹果表面是“单连通的”，而轮胎面不是。大约在一百年以前，庞加莱已经知道，二维球面本质上可由单连通性来刻画，他提出三维球面(四维空间中与原点有单位距离的点的全体)的对应问题。这个问题立即变得无比困难，从那时起，数学家们就在为此奋斗。庞加莱

36、猜想，已被我国中山大学朱熹平教授和旅美数学家、清华大学兼职教授曹怀东破解了。难题四 黎曼(Riemann)假设 有些数具有不能表示为两个更小的数的乘积的特殊性质，例如，2，3，5，7，等等。这样的数称为素数；它们在纯数学及其应用中都起着重要作用。在所有自然数中，这种素数的分布并不遵循任何有规则的模式；然而，德国数学家黎曼(1826-1866)观察到，素数的频率紧密相关于一个精心构造的所谓黎曼函数z(s)的性态。著名的黎曼假设断言，方程z(s)=0的所有有意义的解都在一条直线上。这点已经对于开始的1,500,000,000个解验证过。证明它对于每一个有意义的解都成立将为围绕素数分布的许多奥秘带来

37、光明。 难题五 杨米尔斯(Yang-Mills)存在性和质量缺口 量子物理的定律是以经典力学的牛顿定律对宏观世界的方式对基本粒子世界成立的。大约半个世纪以前，杨振宁和米尔斯发现，量子物理揭示了在基本粒子物理与几何对象的数学之间的令人注目的关系。基于杨米尔斯方程的预言已经在如下的全世界范围内的实验室中所履行的高能实验中得到证实：布罗克哈文、斯坦福、欧洲粒子物理研究所和驻波。尽管如此，他们的既描述重粒子、又在数学上严格的方程没有已知的解。特别是，被大多数物理学家所确认、并且在他们的对于“夸克” 的不可见性的解释中应用的“质量缺口”假设，从来没有得到一个数学上令人满意的证实。在这一问题上的进展需要在

38、物理上和数学上两方面引进根本上的新观念。难题六 纳维叶斯托克斯(Navier-Stokes)方程的存在性与光滑性 起伏的波浪跟随着我们的正在湖中蜿蜒穿梭的小船，湍急的气流跟随着我们的现代喷气式飞机的飞行。数学家和物理学家深信，无论是微风还是湍流，都可以通过理解纳维叶斯托克斯方程的解，来对它们进行解释和预言。虽然这些方程是19世纪写下的，我们对它们的理解仍然极少。挑战在于对数学理论做出实质性的进展，使我们能解开隐藏在纳维叶斯托克斯方程中的奥秘。难题七 贝赫(Birch)和斯维纳通戴尔(Swinnerton-Dyer)猜想 数学家总是被诸如x2+y2=z2那样的代数方程的所有整数解的刻画问题着迷。

39、欧几里德曾经对这一方程给出完全的解答，但是对于更为复杂的方程，这就变得极为困难。事实上，正如马蒂雅谢维奇(Yu.V.Matiyasevich)指出，希尔伯特第十问题是不可解的，即，不存在一般的方法来确定这样的方法是否有一个整数解。当解是一个阿贝尔簇的点时，贝赫和斯维讷通戴尔猜想认为，有理点的群的大小与一个有关的函数z(s)在点s=1附近的性态。特别是，这个有趣的猜想认为，如果z(1)等于0，那么存在无限多个有理点(解)，相反，如果z(1)不等于0，那么只存在有限多个这样的点。由上看出，NP完全问题排在七个“千僖年数学难题”百万美元大奖的首位，足见他的显赫地位和无穷魅力。NP完全问题是NP类中“

40、最难”的问题，也就是说它们是最可能不属于P类的。这是因为任何NP中的问题可以在多项式时间内变换成为任何特定NP完全问题的一个特例。多流水线调度实际上是一个NP完全问题数学上著名的NP问题，完整的叫法是NP完全问题。在第6节中我们会对NP完全问题给出较详细的阐述。4. 可计算性可计算性理论是计算机科学的理论基础之一。早在30年代，图灵对存在通用图灵机的逻辑证明表明，制造出可通过编程解决任何计算的通用计算机是可能的，这影响了40年代出现的存储程序计算机（即诺伊曼型计算机）的设计思想。可计算性理论确定了哪些问题可能用计算机解决，哪些问题不可能用计算机解决。研究计算的一般性质的数学理论，也称算法理论或

41、能行性理论。它通过建立计算的数学模型（例如抽象计算机），精确区分哪些是可计算的，哪些是不可计算的。计算的过程就是执行算法的过程。可计算性理论的重要课题之一，是将算法这一直观概念精确化。算法概念精确化的途径很多，其中之一是通过定义抽象计算机，把算法看作抽象计算机的程序。通常把那些存在算法计算其值的函数叫可计算函数。因此，可计算函数的精确定义为：能够在抽象计算机上编出程序计算其值的函数。这样就可以讨论哪些函数是可计算的，哪些函数是不可计算的。4.1 可计算性的产生可计算性理论起源于对数学基础问题的研究。20世纪30年代，为了讨论是否对于每个问题都有解决它的算法，数理逻辑学家提出了几种不同的算法定义

42、。K.哥德尔和S.C.克林尼提出了递归函数的概念，A.丘奇提出转换演算， A.M.图灵和E.波斯特各自独立地提出了抽象计算机的概念（后人把图灵提出的抽象计算机称为图灵机），并且证明了这些数学模型的计算能力是一样的，即它们是等价的。著名的丘奇-图灵论题也是丘奇和图灵在这一时期各自独立提出的。后来，人们又提出许多等价的数学模型，如A.马尔可夫于40年代提出的正规算法（后人称之为马尔可夫算法），60年代前期提出的随机存取机器模型（简称 RAM）等。50年代末和60年代初，胡世华和J.麦克阿瑟等人各自独立地提出了定义在字符串上的递归函数。4.2 可计算性的内容 若m和n是两个正整数，且mn，求m和n的

43、最大公因子的欧几里得算法可表示为：E1求余数以n 除m 得余数r。E2余数为0吗?若r0，计算结束，n即为答案；否则转到步骤E3。E3互换把m的值变为n，n的值变为r，重复上述步骤。依照这三条规则指示的步骤，可计算出任何两个正整数的最大公因子。可以把计算过程看成执行这些步骤的序列。我们发现，计算过程是有穷的，而且计算的每一步都是能够机械实现的（机械性）。为了精确刻画算法的特征，人们建立了各种各样的数学模型。4.3 重要概念4.3.1 图灵机一种在理论计算机科学中广泛采用的抽象计算机，它是图灵在1936年提出的，用于精确描述算法的特征。可用一个图灵机来计算其值的函数是可计算函数，找不到图灵机来计

44、算其值的函数是不可计算函数。可以证明，存在一个图灵机U，它可以模拟任何其他的图灵机。这样的图灵机U称为通用图灵机。通用图灵机正是后来出现的存储指令的通用数字计算机的理论原型。4.3.2 转换演算 一种定义函数的形式演算系统，是A.丘奇于1935年为精确定义可计算性而提出的。他引进记号以明确区分函数和函数值，并把函数值的计算归结为按一定规则进行一系列转换，最后得到函数值。按照转换演算能够得到函数值的那些函数称为可定义函数。 4.3.3 丘奇-图灵论题 可计算性理论的基本论题，也称图灵论题，它规定了直观可计算函数的精确含义。丘奇论题说：可定义函数类与直观可计算函数类相同。图灵论题说：图灵机可计算函

45、数类与直观可计算函数类相同。图灵证明了图灵机可计算函数类与可定义函数类相同。这表明图灵论题和丘奇论题讲的是一回事，因此把它们统称为丘奇图灵论题。直观可计算函数不是一个精确的数学概念，因此丘奇-图灵论题是不能加以证明的。30年代以来，人们提出了许多不同的计算模型来精确刻划可计算性，并且证明了这些模型都与图灵机等价。这表明图灵机和其他等价的模型确实合理地定义了可计算性，因此丘奇图灵论题得到了计算机科学界和数学界的公认。4.3.4 递归函数 原始递归函数 自变量值和函数值都是自然数的函数，称为数论函数。原始递归函数是数论函数的一部分。首先规定少量显然直观可计算的函数为原始递归函数，它们是：函数值恒等

46、于0的零函数C0，函数值等于自变量值加1的后继函数S，函数值等于第i个自变量值的n元投影函数P。然后规定，原始递归函数的合成仍是原始递归函数，可以由已知原始递归函数简单递归地计算出函数值的函数仍是原始递归函数。例如，和函数f(x，y)=x+y可由原始递归函数P(1)1和S递归地计算出函数值 f(x，0)=P(1)1(x)f(x，S(y)=S(f(x，y)比如，f(4,2)可这样计算，首先算出f(4,0)=P(1)1(4)=4，然后计算f(4,1)=S(f(4,0)=S(4)=5f(4,2)=S(f(4,1)=S(5)=6因此，和函数是原始递归函数。显然，一切原始递归函数都是直观可计算的。许多常

47、用的处处有定义的函数都是原始递归函数，但并非一切直观可计算的、处处有定义的函数都是原始递归函数。部分递归函数 为了包括所有的直观可计算函数，需要把原始递归函数类扩充为部分递归函数类。设g(x1，xn，z)是原始递归函数，如果存在自然数z使g(x1，xn，z)=0，就取f(x1，xn)的值为满足g(x1，xn，z)=0的最小的自然数z；如果不存在使g(x1，xn，z)=0的自然数z，就称f(x1，xn)无定义。把如上定义的函数f加到原始递归函数类中，就得到部分递归函数类。因为不能保证如上定义的f在一切点都有定义，故称其为部分函数。处处有定义的部分递归函数称为递归函数。部分递归函数类与图灵机可计算

48、函数类相同。对于每个n元部分递归函数f，可以编一个计算机程序P，以自然数x1，xn作为输入，若f(x1，xn)有定义，则P函数值执行终止并输出的f(x1，xn)，否则P不终止。递归集 递归集最初是对于元素都是自然数的集合定义的，它们是有算法确定每个自然数是否为其元素的集合。可以将递归集的概念推广到其他集合。所讨论的对象的全体称为域，如果有算法确定域中任意元素是否属于A，则称A为递归集。对于每个递归集，可以编一个计算机程序，以域中任意元素作为输入，计算执行该程序都可给出适当的输出，表明该元素是否属于这个递归集。有许多集合不是递归集。递归可枚举集 如果对于集合A可以编一个程序P，输入域中任意元素x

49、，若xA，则P的执行将终止并输出“是”，否则P 的执行不终止，就称A为递归可枚举集。A为递归可枚举集的充分必要条件是可以编一个程序枚举A的元素，即打印A的元素，使得对于 A中任意元素，只要时间足够长总会在打印纸上出现。递归集都是递归可枚举集，但有些递归可枚举集不是递归集。有许多集合不是递归可枚举集。4.3.5 可判定性和半可判定性 判定问题是无穷多个同类个别问题的总称。例如，2是不是素数？6是不是素数？这些都是个别问题，把这类个别问题概括起来，就得到一个判定问题：任意给定的正整数是不是素数？这里的正整数集合称为该判定问题的域，给定域中的一个元素，判定问题就对应一个个别问题。对于一个判定问题，如

50、果能够编出一个程序，以域中任意元素作为输入，执行该程序就能给出相应的个别问题的答案，就称该判定问题为可判定的。例如，“任意正整数是不是素数”这个问题就是可判定的。对于集合A，域中任意元素是否属于它的问题称为集合 A对应的判定问题。集合是递归集的充分必要条件为对应的判定问题是可判定的。因此，全体素数的集合是递归集。对于一个判定问题，如果能够编出一个程序P，以域中任意元素作为输入，当相应的个别问题的解答是肯定的时候，P 的执行将终止并输出“是”，否则P 的执行不终止，就称该判定问题为半可判定的。可判定的问题总是半可判定的。集合是递归可枚举集的充分必要条件为对应的判定问题是半可判定的。图灵在1936

51、年证明，图灵机的停机问题是不可判定的，即不存在一个图灵机能够判定任意图灵机对于任意输入是否停机。图灵机的停机问题是半可判定的。图灵机的停机问题是很重要的，由它可以推出计算机科学、数学、逻辑学中的许多问题是不可判定的。5. 计算复杂性计算复杂性是现代理论计算机科学中最重要的分支之一，它研究各种问题类在计算时所需要耗费的时间、空间等资源的多少，是可计算性理论的新发展。5.1 从可计算性到计算复杂性 什么样的问题类是可计算的？这是数学、数理逻辑学和早期计算机科学所关心的一个重要问题。为了回答这个问题，可以给出一个计算的模型，然后规定，凡是这个模型能计算的问题类就称作可计算的，否则就称为不可计算的。于

52、是产生了各种计算的模型：图灵机、递归函数、 演算、马尔可夫算法和递归算法等。但是，会不会有一类问题，在一个模型中是可计算的，而在另一个模型中却是不可计算的呢？如果这样，一个问题类的可计算性就依赖于模型，而不是问题类本身的性质了。著名的丘奇图灵论题回答了这个问题。这个论题说：“凡是合理的计算模型都是等价的，即一个模型能算的问题类别的模型也能算，一个模型不能算的别的模型也不能算。”这个论题不是一个严格的命题，无法给出一般的证明，但可以对一个个具体的模型去验证它的正确性。然而，对于一个问题类，只知道它能否计算还很不够，更有实际意义的是要知道计算起来要耗费多少时间，要用多大的空间来存储计算的中间结果等

53、等。为了回答这些进一步的问题，就产生了计算复杂性理论。5.2 资源计算时间、存储大小都称为资源。一般来说，各种模型的主要资源有并行时间、空间和串行时间三种。严格地讲，每一种资源的定义都依赖于特定的计算模型。对各种计算模型，资源的定义虽不一样，但主要的可分为三类。例如，对于多带的图灵机，就有串行时间、空间、巡回等资源。串行时间（简称时间） 它是计算过程中的总运算量，即把计算分成一些原始的步骤，完成这些步骤所需要的总时间。空间 它是为了保存中间结果所需要的存储器的大小。例如在计算时用一块黑板来打草稿，每一单位面积假定可以写一个符号，不用了还可以擦掉。在计算时所需黑板面积就是空间。并行时间它是并行计

54、算所需要的时间，亦即如果多人或多处理机协同计算，解决一个问题所需要的时间。5.3 问题的大小和复杂性的度量和可计算性一样，复杂性总是对于一个特定的问题类来讨论的，它包括无穷多个个别问题，有大有小。例如，对矩阵乘法这样一个问题类，相对地说，100阶矩阵相乘是个大问题，而二阶矩阵相乘就是个小问题。可以把矩阵的阶n作为衡量问题大小的尺度。又如在图论问题中，可以把图的顶点数n作为衡量问题大小的尺度。一个个别问题在计算之前，总要用某种方式加以编码，并可把这个编码的长度 n作为衡量问题大小的尺度。当给定一个算法以后，计算大小为n的问题所需要的时间、空间等就可以表示为 n的函数。这个函数就可作为该算法的时间

55、或空间复杂性的度量。严格地讲，是这个特定的问题类在某一特定计算模型中某一特定算法的复杂性之度量。当要解决的问题越来越大时，时间、空间等资源耗费将以什么样的速率增长，即当n趋向于无穷大时，这个函数的性状如何，增长的阶是什么，这就是计算复杂性理论所要研究的主要问题。5.3.1 巡回和周相在上面提到的模型中，有的是串行模型，有的则是并行模型。如前所述，并行模型的串行时间相当于计算过程中的总运算量。至于串行模型的并行时间，可以认为它是一个叫作巡回的量。简而言之，巡回是计算过程中周相的总数。而周相则是计算过程中的一个阶段，在此阶段内写入工作空间的信息不会在同一阶段中读出。由此可见，串行模型的巡回相应于并

56、行模型的并行时间。对于一个问题类而言，存在一个高速并行算法的充要条件是可以找到一个具有小的巡回数的串行算法。5.3.2 相似性原理如上所述，一个问题类的时间、空间等资源的复杂性是依赖于模型的：在有的模型中较高，在另一些模型中则较低。现在较为重要而有特色的计算模型有：多带图灵机器、多变址随机存取机器、存储修改机器、齐一线路、向量机器、硬件修改机器等等。这样一来，复杂性的问题仍然没有一个统一的客观依据。相似性原理解答了这个问题。按此原理，一个问题类内在的并行时间、空间和串行时间的复杂性在所有理想的计算模型中都没有本质的差异。用数学的说法，各种模型可以互相模拟，而且模拟者需用的并行时间、空间和串行时

57、间都分别不超过被模拟者所需的并行时间、空间和串行时间的一个多项式，三者同时成立。所以在只差一个多项式的范围内，复杂性的确是一个不依赖于模型的客观实在。这是丘奇图灵论题在复杂性理论中的新发展。对于上面提到的计算模型，相似性原理已被证明是正确的。以多带图灵机和向量机器为例，可以证明下面的相似性定理：设n是输入字符串的长度，它代表问题的大小。对于任何一个多带图灵机，设它的巡回为R(n)，空间为S(n)，串行时间为T(n)，则一定有一个向量机器来模拟它，使得存在一个多项式p，向量机器的并行时间R1(n)，空间S1(n)和串行时间T1(n)满足 R1(n)p(R(n)S1(n)p(S(n)T1(n)p(

58、T(n)在以上结论中把多带图灵机和向量机器的位置对调一下也成立。这说明在多项式相关联意义下，这两个模型没有本质的区别。因此，巡回是串行模型的虚拟并行时间。5.3.3 代数复杂性 相似性原理所涉及的模型主要研究计算中按位运算的总量时间，按位计的中间结果存储量空间和计算的深度(并行时间)等等，所以可称为按位的复杂性。代数的复杂性理论则研究在一个代数系统中（例如实数域中）从给定变量出发去计算某些函数所需要的代数运算（例如加法、乘法）代数判断（例如大于或等于）的次数(时间)，所需中间变元的个数(空间)，计算的深度(并行时间)等等。在实际运算中，既不能给出一个无限长的实数，也不能在一个单位时间内完成两个实数的乘法。真正的算术运算都是通过近似小数的按位运算得出来的。所以按位的复杂性具有更为基本的意义。通过下面的例子，可以得到关于代数复杂性的