计算复杂性课件

可计算性与计算复杂性李占山1000个图片的拼图，如果没有考虑把握技巧，那么对于每个图片有正反面、左右和对错3种组合8种状态，这样我们把所有图片拼在一起需要考虑81000种状态（步骤）情况拼图，这是一个惊人的数字，用计算机求解在我们的有生之年是看不到结果的。难道这个问题就没有结果了吗？非也，我们人不是在玩这种游戏吗？我只用了一两天甚至更短的时间就成功了，哪有你老师说的那么复杂？那样不是很郁闷吗？我拼图成功很是快乐，为什么？拼图游戏从拼图游戏到解现实生活中的实际问题的解决---同学，游戏不是这样玩的！我们的课程可以使你从可郁闷性与郁闷复杂性到可快乐性与快乐复杂性的。怎么办？分类分解问题呗！首先把图片都翻到相同一面，最坏时要做1000次，如果图片字母标号有20种，然后把它们根据字母标号分成20子类，每一子类再根据字母正反分为2个子子类，同样拼图时相邻的图片是交错排列的，按照这样的分类方法进行拼图看看最坏时我们需要多少个步骤？玩游戏是一门学问呦！1000+1000+20250个状态（步骤），这些状态步骤完全在你的有限时间掌控之中，因此能够在一两天甚至更短时间内完成拼图任务。嗷！原来是这样的呀！看来学好这门课会使我们从可郁闷性与郁闷复杂性到可快乐性与快乐复杂性的！！！为了学好这门课程我们有必要介绍这门课程的本质与定位以及一些重要历史人物，他们是？？？？？

计算学科（ComputingScience）即我们所熟悉的计算机科学与技术(ComputerScienceandTechnology)。计算学科是对描述和变换信息的算法过程，包括其理论、分析、设计、效率分析、实现和应用等进行的系统研究的一门学科。它涉及计算过程的分析如可计算性、算法，研究有关计算机的各种现象、揭示其规律与本质如计算机的设计和使用、可计算性硬件和软件的实际实现问题。

计算学科的基本问题是能行与效率的问题,即它的核心问题是“能行”问题(Practicability)：1)什么是（实际）可计算的？什么是（实际）不可计算的？2)如何保证计算的自动性、有效性及正确性？

1985年春，ACM（美国计算机协会）和IEEE－CS（国际电子电气工程师学会计算机分会）组成联合攻关小组，开始了对“计算作为一门学科”的存在性证明。1989年1月，该小组提交了《计算作为一门学科》（Computingasadiscipline）的报告。第一次给出了计算学科一个透彻的定义，回答了计算学科中长期以来一直争论的一些问题，完成了计算学科的“存在性”证明，还提出了未来计算科学教育必须解决的二个重大问题――整个学科核心课程详细设计及整个学科综述性导引课程的构建。1991年，在这报告的基础上提交了关于计算学科教学计划CC1991（ComputingCurricula1991）。2001年12月，提交了最终的CC2001报告。

《计算作为一门学科》报告及CC1991、CC2001一起解决了三个重要问题：第一个重大问题（计算作为一门学科的存在性证明）的解决。对学科本身的发展至关重要。如果在众多分支领域都取得了重大成果并已得到广泛应用的“计算”，连作为一门学科的地位都不清楚，那么它的发展势必要受到很大的限制。

第二个重大问题（整个学科核心课程详细设计）的解决，将为高校制定计算机教学计划奠定基础。确定一个公认的本科生应该掌握的核心内容，将避免教学计划设计中的随意性，从而为我们科学地制定教学计划奠定基础。

第三个重大问题（整个学科综述性导引课程的构建）的解决，将使人们对整个学科的认知科学化、系统化和逻辑化。如果人们对计算学科的认知能建立在公理化的基础之上，则该学科可被认为是严谨的科学、成熟的学科，从而有助于它的发展，并将由此而得到人们的尊重。

攻关小组的结论是：计算学科所研究的根本问题是能行问题（什么能被（有效地）自动进行）。计算学科的基本原理已纳入理论、抽象和设计这3个具有科学技术方法意义的过程中。学科的各分支领域正是通过这3个过程来实现它们各自的目标。而这3个过程要解决的都是计算过程中的“能行性”和“有效性”问题。

与数学相比，电子技术的重要性对计算科学而言不如数学，因为数学提供了计算科学最重要的学科思想和方法论基础，而电子技术只提供了电子计算机的实现技术，它仅仅只是对计算科学许多思想和方法的一种当前最现实、最有效的实现技术手段而已。当科学技术的手段提到发展时，完全有可能有某一项新技术归结为有效地取代电子技术（如光技术、生物技术等等），但计算科学的数学基础可能变化不大。

从事计算科学的人都知道，计算科学中不仅许多理论是用数学描述的，而且许多技术也是用数学描述的。大多数计算科学理论不仅仅是对研究对象变化规律的陈述，而且由于能行性这一本质的核心问题和特点的作用，理论描述中常通过方法折射出技术的思想和步骤，而从理论通过方法跨越到技术则完全取决于理论的深刻认识和理解。一个人如果看懂了以形式化方法描述的技术文献，自然明白技术上应该怎样去做。

至于计算机技术专业的学生为何要学习数学这个问题的答案，了解了上面所讲的计算学科与数学的关系后就不言而喻了：计算机科学植根于数学，但又不同于数学，从而可计算理论的基础知识就需要掌握，因为这能够提高我们本身的逻辑推理能力、抽象思维能力和形式化思维能力，从而今后在学习任何一门计算机科学的专业主干课程时，都不会遇上任何思维理解上的困难。

当前计算机科学在发展过程中面对着如下两个问题：

一是信息革命要求计算机科学要将计算机的应用扩大到包含所有的问题领域和深入到每个问题领域的深处而越来越细致越来越复杂；二是一旦让计算机去解决问题，那么计算机应自动地在有限和有效的时间内得出解。前者指出计算机科学的任务就是要用计算机的硬件、外设和软件构成一个系统，使得许多不同领域的问题都能在这样的计算机系统中得到解决。为了完成这个任务，就必须用一种符号语言构成一个包括了不同领域的通用模型。

计算理论就是指出构成一个包括了不同领域的通用模型的思维方法，并且告诉我们怎样用不同的语言（符号语言、图形语言、逻辑语言等）从最简单的对象（集合）出发表示通用模型。后者指出计算机科学必须了解让计算机去解决问题在通用模型中的结构，由于要求在有限和有效时间内计算机自动完成，那么问题求解的方法必然是构造性的。

(2)从计算机科学学生能力角度培养的看计算理论的作用。计算机出现的五十多年间，人们追求着和出现了许多计算机信息革命带来的信息产品，但是信息产品受工业产品的观念上的影响，使得计算机科学的学科发展带来了偏差，使得整个学科的发展都是“软件跟着硬件走”。我们不能将自己的学生培养成计算机系统的奴隶，而应该培养成计算机系统的主人，我们的学生不能给计算机系统所塑造，将他们变成计算机，而是教育学生怎样地塑造计算机系统。

在计算机科学知识掌握的过程中应是“硬件跟着软件走，软件跟着模型走，模型跟着学科实际应用走；学科实际应用跟着自然走”。而最主要的培养环节应该是软件跟着模型走，模型跟着学科实际应用走。关于学生的培养目标就是要培养自己的学生能够根据实际应用问题提出计算机应用的模型，并用硬件和软件资源去构造计算机系统去完成模型中所提出来的工作。

首先，计算机系统要解决的问题并不是个别的问题，也并不是某个领域上的特殊问题，要解决某个领域的所有能用计算机进行计算的问题，因此，关于计算机科学的思维方法必须是在足够通用的层面上的思维方法。如果所掌握或所习惯的思维方法仅限制在是某些特殊的领域，那么，随着计算机应用的不断扩大和计算机信息革命的不断扩大，将会使得思维的方法带有很大的局限性。当然，最通用的层面是自然层面，然而，自然层面上的对象还不能为现代计算机(现代计算模型)所了解。因为，我们选择塑造计算机系统的层面既带有最大的通用性，又能为现代计算机系统所了解的层面。在现代计算技术的支持下，这个层面就是符号处理层面。

其次，我们是要去塑造计算机系统，我们的所有思维都要立足于能“塑造”性，因此，思维的可构造性，即在考虑构成计算机系统的所有对象都必须能够有某种方法在有限的时间内构造出来。因此塑造计算机系统的基本思维是构造性思维。以上描述了计算理论的学科定位下面我们来看相关的历史人物简介计算理论的开拓者—图灵阿兰·图灵，1912年6月23日出生于英国伦敦。其祖父曾获得剑桥大学数学荣誉学位，但他父亲的数学才能平平。因此，图灵的家庭教育，对他以后在数学及计算机方面的成就并没有多少帮助。

小时侯的图灵生性活泼好动，很早就表现出对科学的探索精神。据他母亲回忆，3岁时，小图灵就进行了他的首次实验，尝试把一个玩具木头人的小胳膊、小腿掰下来栽到花园里，等待长出更多的木头人。到了8岁，他更开始尝试写一部科学著作，题目为《关于一种显微镜》。在这部很短的书中，天才儿童图灵拼错了很多单词，句法也有些问题，但写得还能让人看懂，很像那么一回事儿。在书的开头和结尾，他都用同一句话“首先你必须知道光是直的”作前后呼应，但中间的内容却很短，短得破了科学著作的记录。图灵曾说:“我似乎总想从最普通的东西中弄出些名堂。”就连和小朋友们玩足球，他也能放弃当前锋进球这样出风头的事，只喜欢在场外巡边，因为这样能有机会去计算球飞出边界的角度。他的老师认为:“图灵的头脑思维可以像袋鼠一样进行跳跃。”图灵是个天才。他16岁就开始研究爱因斯坦的相对论。1931年，图灵考入剑桥大学国王学院，开始他的数学生涯，研究量子力学、概率论和逻辑学。在校期间，图灵还是现代语言哲学大师维特根斯坦班上最出色的学生。他对由剑桥大学的罗素和怀特海创立的数理逻辑很感兴趣。数理逻辑的创建，主要是为了对付“悖论”。“悖论”(paradox)是人类思维中最狡猾的两面派，最早起源于古希腊克里特岛上有个叫爱皮梅尼特的“智者”，他说:“所有的克里特岛人都说谎”。我们可以把它简化为:“我说的这句话是假话”。这就出现一种两面都无法自圆的怪圈:如果他没有说谎，那他这句话是错的，他是在说谎;如果他真的在说谎，那他说自己在说谎是对的，所以他又没有说谎。罗素和怀特海把它从逻辑、集合论以及数论中驱逐出去，最后又想尽办法归入《数学原理》之中。

图灵一上大学，就迷上了《数学原理》。在1931年，著名的“哥德尔定理”出现后(该定理认为没有一种公理系统可以导出数论中所有的真实命题，除非这种系统本身就有悖论)，天才的图灵在数理逻辑大本营的剑桥大学提出一个设想:能否有这样一台机器，通过某种一般的机械步骤，能在原则上一个接一个地解决所有的数学问题。大学毕业后，图灵去美国普林斯顿大学攻读博士学位，还顺手发明过一个解码器。在那里，他遇见了冯·诺依曼，后者对他的论文击节赞赏，并随后由此提出了“存储程序”概念。图灵学成后又回到他的母校任教。在短短的时间里，图灵就发表了几篇很有份量的数学论文，为他赢得了很大的声誉。

在剑桥，图灵可称得上是一个怪才，一举一动常常出人意料。他是个单身汉和长跑运动员。在他的同事和学生中间，这位衣着随便、不打领带的著名教授，不善言辞，有些木讷、害羞，常咬指甲，但他更多地以自己杰出的才智赢得了人们的敬意。图灵每天骑自行车上班，因为患过敏性鼻炎，一遇到花粉，就会鼻涕不止，大打喷嚏。于是，他就常常在上班途中戴防毒面具，招摇过市，这早已成为剑桥的一大奇观。图灵的自行车经常半路掉链子，但他就是不肯去车铺修理。每次骑车时，他总是嘴里念念有词，在心里细细计算，这链条也怪，总是转到一定的圈数就滑落了，而图灵竟然能够做到在链条下滑前一刹那停车，让旁观者佩服不已，以为图灵在玩杂技。后来图灵又居然在脚踏车旁装了一个小巧的机械记数器，到圈数时就停，歇口气换换脑子，再重新运动起来。

1936年，图灵向伦敦权威的数学杂志投了一篇论文，题为《论数字计算在决断难题中的应用》。在这篇开创性的论文中，图灵给“可计算性”下了一个严格的数学定义，并提出著名的“图灵机”(TuringMachine)的设想。“图灵机”不是一种具体的机器，而是一种思想模型，可制造一种十分简单但运算能力极强的计算机装置，用来计算所有能想像得到的可计算函数。装置由一个控制器和一根假设两端无界的工作带(起存储器的作用)组成。工作带被划分为大小相同的方格，每一格上可书写一个给定字母表上的符号。控制器可以在带上左右移动，它带有一个读写头，可读出控制器所访问的格子上的符号，也能改写或抹去这一符号，最后便会得出一个你期待的结果。外行人看了会坠入云里雾里，而内行人则称它是“阐明现代电脑原理的开山之作”，并冠以“理想计算机”的名称。这篇论文在纸上谈了一把兵，创造出一个“图灵机”来。但现代通用电脑确实是用相应的程序来完成任何设定好的任务。这一理论奠定了整个现代计算机的理论基础。“图灵机”更在电脑史上与“冯·诺依曼机”齐名，被永远载入计算机的发展史中。1931年，年轻的法国数学家赫尔布兰德（JacquesHerbrand，1908～1931）对递归函数进行了研究，并给著名逻辑学家哥德尔（KurtGödel，1906～1978）写信叙述了自己的研究结果。哥德尔当时正处于自己一生中最重大的成果—哥德尔不完全性定理的研究时期，他没有仔细看赫尔布兰德的来信内容，因此没有立即对赫尔布兰德的工作做出回应。那一年的夏天，年仅23岁的赫尔布兰德在攀登阿尔卑斯山时不幸遇难，他的工作因此被暂时埋没了。

与赫尔布兰德的研究差不多同时，1931年秋天，普林斯顿大学的美国逻辑学家丘奇（AlonzoChurch，1903～1995）也在积极从事逻辑及算法的研究，并且发展出了一种新的逻辑体系。丘奇在普林斯顿开了一门逻辑课，他让自己的两个学生克林（StephenKleene，1909～1994）与罗瑟（JohnRosser，1907～1989）对这一体系做细致的研究。两个学生都是一流好手，他们的研究很快就有了结果，但这结果大大出乎丘奇的意料。他们发现丘奇的那套体系竟然是自相矛盾的！命运似乎只有一个：放弃。幸运的是，丘奇的那套体系中有一个组成部分是自洽的，因此可以保留下来，这部分叫做兰姆达运算（λ－calculus）。这种兰姆达运算可以用来定义函数，而所有用兰姆达运算定义的函数都是可以有效计算的。在对兰姆达运算做了研究之后，丘奇提出了一个大胆的猜测，他猜测所有可以有效计算的函数都可以用兰姆达运算来定义。于是克林开始进行研究，结果克林和丘奇得到一类可计算的函数，他们称之为A可定义函数。

1934年春天，哥德尔在普林斯顿大学做了一系列讲演。丘奇向到普林斯顿大学访问的哥德尔介绍了他的猜测，哥德尔却不以为然。丘奇不服气，请哥德尔给出一个他认为合适的描述。一两个月后，哥德尔就给出了一种完全不同的描述，这种描述的基础正是3年前赫尔布兰德在给他的信中叙述的结果。哥德尔对这一结果进行了完善，这一结果被人们称为赫尔布兰德－哥德尔递归函数。与此同时，丘奇和克林在1936年分别发表论文，证明A可定义函数类正好就是一般递归函数类。有了这个有力的证据，丘奇于是公开发表他的"论点"。这样，丘奇与哥德尔各自给出了一种体系，描述可以有效计算的函数。丘奇与克林很快证明，这两种看上去完全不同的描述方式实际上是彼此等价的。

两位著名逻辑学家的工作殊途同归，大大增强了丘奇的信心。他相信人们已经找到了可以有效计算的函数的普遍定义。但哥德尔及其他一些人对此却仍然怀有疑虑。最终打消这种疑虑的是英国数学家图灵（AlanTuring，1912～1954）。

1937年图灵证明了用图灵机可计算的函数类与可定义函数类是一致的，当然，也就和一般递归函数类相重合。这样一来，丘奇的论点与图林的论点就是一回事。当时许多人对于丘奇的论点表示怀疑，由于图林的思想表述得如此清楚，从而消除了许多人的疑虑，哥德尔就是其中一位。从这时起大家对于丘奇-图灵论点一般都抱支持的态度了。数理逻辑学家歌德尔

1947年美国数学家波斯特（EmilPost，1897～1954）找到了第一个逻辑领域以外的不可判定命题。波斯特是一位有着深刻洞察力的逻辑学家，7岁时随父母从波兰移民到美国，是美国逻辑学的先驱之一。他10年前就得到了与哥德尔不完全性定理相似的结果，由于想对结果作更全面的分析而没有及时发表。他也是最早意识到希尔伯特第十问题可能会有否定答案的数学家之一。1944年，他在一篇文章中明确提出希尔伯特第十问题“期待一个不可解性证明”。当时波斯特在纽约市立大学任教，他的这一观点深深打动了一位学生，使后者走上了毕生钻研希尔伯特第十问题的征途。这位学生名叫戴维斯（MartinDavis，1928～），是解决希尔伯特第十问题的关键人物。图灵奖与计算理论图灵奖是由ACM于1966年首次设立的奖项,它是为了纪念“计算机科学之父”图灵而设立的,专门奖励那些在计算机科学研究中做出创造性贡献、推动了计算机科学技术发展的杰出科学家。虽然没有明确规定，但从实际执行过程来看，图灵奖偏重于在计算机科学理论和软件方面作出贡献的科学家。奖金金额不算太高，设奖初期为2万美元，1989年增至2万5千美元，奖金通常由计算机界的一些大企业提供（通过与ACM签定协议）。由于图灵奖对获奖者要求极高，评奖程序又极严，一般每年只奖励一名计算机科学家，只有极少数年度有两名合作者或在同一方向作出贡献的科学家共享此奖。因此它是计算机界最负盛名、最崇高的一个奖项，有‘计算机界的诺贝尔奖“之称。从1966年到2000年共有41位科学家获此殊荣，在这些学者中从事计算复杂性理论研究的有11人，几乎占四分之一。他们是？？？？1976年图灵奖获得者拉宾和斯科特1976年的图灵奖由当时在以色列希伯莱大学的教授拉宾和英国牛津大学的数理逻辑教授斯科特共同获得。他们是师兄弟，两人在50年代中期先后师从于著名的数理逻辑与计算机科学家丘奇（他对可计算性理论做出了实质性贡献，如判定问题的解、演算的发明，90岁还在发表论文，图灵也是他的学生），并在有限自动机及其判定问题的研究中进行合作，奠定了非确定性有限自动机的理论基础，之后，他们的研究方向不尽相同，拉宾侧重于计算理论，而斯科特侧重于逻辑学在计算机科学中的应用，在各自的领域中又分别获得重大成果，做出了创造性贡献。计算机科学家、数理逻辑学家丘奇拉宾是1931年出生于德国的布雷斯劳的犹太人，1948年以色列建国以后成为以色列公民，20世纪50年代拉宾博士毕业于普林斯顿大学，使拉宾成名的是IBM研究中心1957年向他和师弟斯科特提供的允许他们做自己感兴趣的工作。于是他们二人联手研究图灵机----有限状态自动机。他们定义了一种新的、“非确定性”行为的有限状态自动机(NDFSA)，这种机器在读去到一定的输入后，有一个可以进入的可能的新的状态的‘菜单’可供选择，这样对给定的输入计算便不单一了，每个选择代表一种可能的计算。拉宾和斯科特将图灵的有限状态自动机从确定性一种扩展到非确定的另一种形式，极大地推动了有限状态自动机理论的发展，虽然非确定性有限状态自动机的能力并不比确定性的有任何增加（拉宾和斯科特已经证明他们等价），但是它可以简化机器描述和加快解题速度。后来的时间证明，非确定性有限状态自动机在机器翻译、文献检索和字处理程序等应用中都起到了重要作用。他们的研究结果发表于2年后的1959年IBM杂志上，题目为“有限自动机及其判定问题”。1958年夏天拉宾又来到IBM，当时“人工智能之父”麦卡锡（1971年图灵奖获得者）正在那里研究往巴克斯（1977年图灵奖获得者）发明的FORTRAN语言中加入表处理功能，他给拉宾出了一道难题：设计一种口令即使口令被敌方窃取，也无法进入系统。拉宾经过艰苦探索，终于利用冯诺伊曼开发的一个单向函数解决了这个问题。正是这个问题促使拉宾进一步研究计算任务的最小计算量这一一般性问题，也就是计算的固有难度问题，从而使拉宾成为最早研究计算复杂性问题的先驱之一。他的研究结果“计算速度和递归集合的分类”与“函数的计算难度和递归集合的偏序”分别于1959和1960年在耶路撒冷发表。论文中虽然没有用“计算复杂性‘这个名词而用了”计算速度“和”计算难度“，但学术界公认这两篇论文是研究计算复杂性的最早、最权威的论文中的两篇，对1964年正式提出”计算复杂性“这一术语的哈特马尼斯和斯特恩斯（这2人是1993年图灵奖获得者，后面介绍）以及计算复杂性理论的另一奠基人布卢姆（1995年图灵奖获得者，后面介绍）都产生了深刻影响。其中布卢姆正是听到了拉宾的有关演讲才开始研究计算复杂性并完成博士论文的。斯科特比拉宾小一岁，1932年出生于加利福尼亚，在加州大学伯克利分校获得学士学位后，进入普林斯顿大学研究生院深造，与拉宾一起师从于阿隆索丘齐。丘齐对学生要求很严，布置的问题也很难，斯科特开始时难以适应，精神很紧张，经常夜里作恶梦。但经过努力，终于可以从容应付。1957年他与师兄拉宾一起完成了对图灵机的研究，提出了非确定性有限状态自动机的理论以后，在1958年取得博士学位。之后他先后在芝加哥大学、加州大学伯克利分校、斯坦福大学、普林斯顿大学和牛津大学等国际知名高等学府任教。1981年被卡内基梅隆大学聘为计算机科学、数理逻辑和哲学教授。斯科特的主要兴趣和研究方向是逻辑学，包括集合论、模型论、自动机理论、非经典逻辑中的模态逻辑和直觉主义逻辑。斯科特的最大贡献是他与斯特雷奇合作，20世纪60年代提出了程序设计语言的“标志语义模型”为标志语义学奠定了坚实的基础。1978年图灵奖获得者弗洛伊德历届图灵奖得主基本上都有高学历、高学位，绝大多数都有博士学位，但事情总有例外，1978年图灵奖得主、斯坦福大学计算机科学系教授弗洛伊德就是一位“自学成才的计算机科学家”。说他自学成才并不是说他没有接受过高等教育，他是芝加哥大学的毕业生，但学的是文学，1953年获得文学学位，由于当时经济不景气，成为西屋电气公司一名计算机操作员，他不懂计算机，但是个有心人，受过良好高等教育很快对计算机产生了兴趣开始学习相关知识，1956年成为程序员，1965年被卡内基-梅隆大学聘为副教授，1970年聘为教授。大家现在熟知的优先文法，界限上下文文法都是他20世纪60年代提出的，优先文法解决了自底向上的语法分析中的首要问题：如何找到”句柄“，也就是当前需要归约的符号串。1964年与威廉姆斯共同发明了堆排序算法HEAPSORT，这是与英国学者霍尔（1980年图灵奖获得者）发明的QUICKSORT齐名的高效排序算法之一。1982年图灵奖获得者库克NP完全性理论的奠基人库克1939年出生于纽约州的布法罗。1957年中学毕业后，到密歇根大学学科学工程，一年级时选择了一门新开设的课程—程序设计，作为作业，他编了一个ALGOL程序验证歌德巴赫猜想，由此他对计算机科学发生了兴趣。1961年库克获得学士学位以后，转入哈佛大学研究生院深造，第二年就取得了理科硕士学位，他接着攻读了数学博士学位，原先打算研究代数学。然而这时他遇到了一些教师，对他产生了很大的影响，改变了他的兴趣和方向。首先是哈佛研究生院对新兴学科十分重视，虽然当时计算复杂性理论这一学科还处于萌芽和初创时期，他们就邀请了这方面的一些先驱与奠基人，包括拉宾、哈特马尼斯和斯特恩斯，由于对拉宾等人讲学或做报告内容产生兴趣，库克他们的研究和探索的问题发生了极大的兴趣，从而把自己的研究定在这个方向。博士毕业后当时美籍华人数学家王浩提出的图灵机的一种变形叫B机器也引起了他的兴趣。王浩指出，甚至在无限的时间里，要想证明确定谓词演算中的某个公式是否可满足，在计算上都是不可能的，因此王浩从复杂性角度去研究，他的工作给了库克极大的启发，库克从比较单纯和简单的命题演算公式的自动证明入手研究计算复杂性，果然成功了，１９７１年发表了“定理证明过程的复杂性”。在这篇论文中库克首次明确提出了NP完全问题，并奠定了NP完全性理论的基础。以后我们将讲授这些内容。1985年图灵奖获得者卡普发明“分枝限界法”的三栖学者卡普是美国加州大学计算机、数学和工业工程三个系的教授，他被授予图灵奖也是因为在算法设计与分析、计算复杂性理论等方面的创造性贡献，生于１９３５年的卡普兴趣广泛聪明过人，在哈佛大学时文理兼修，1955年先获得文学学士学位，第2年又获得理科硕士学位，之后进入哈佛计算机实验室攻读博士学位，1959年获得数学博士学位后进入IBM。

当时，正是计算机科学的创立时期，高级语言刚刚诞生不久，计算机应用开始被社会所重视并逐渐走向普及。有关数据结构、算法、计算复杂性等课题吸引着众多学者的注意。IBM作为美国乃至世界最大的计算机厂商，理所当然成为这些研究问题的中心之一，集中了大批最优秀的研究人员，在那里卡普主要研究了路径问题、背包问题、覆盖问题、匹配问题，调度问题等，但这些问题都存在组合爆炸问题。２０世纪６０年代初卡普仔细研究了路径问题中的旅行商问题，和同事海尔特经过反复研究，终于提出了一种称为”分枝限界法“的新方法。该方法要点是：对解集合反复进行分枝，每次分枝时都对所得的子集计算最优解的界，如果对某个子集求得的界不优于已知的允许解，则抛弃这个子集不再分枝。否则继续分枝以探索更好的解。１９６８年卡普来到加州大学伯克利分校。这里是计算机科学理论的又一个研究中心，库克、布卢姆（１９８５年图灵奖获得者）等一批知名学者当时都在那里，学术气氛十分浓厚。布卢姆是计算复杂性的主要奠基人之一，库克则与1971年最早提出”NP完全性“问题，在这样环境下，卡普对计算复杂性问题的研究日益深入。１９７２年卡普发表的论文“组合问题中的可归约性”发展和加强了由库克提出的”NP完全性”理论。尤其是库克仅证明了命题演算的可满足性问题是NP完全的，而卡普则证明了从组合优化中引出的大多数经典问题，包括背包问题、覆盖问题、匹配问题、路径问题、调度问题等，都是NP完全问题：只要证明其中任何一个问题是属于P类的，就可以解决计算复杂性理论中的最大的一个难题P=?NP这是卡普论文的主要贡献和意义。1986年图灵奖获得者霍普克洛夫斯特和陶尔扬霍普克洛夫斯特１９３９年出生于西雅图，１９６１年西雅图大学毕业后进入斯坦福大学研究生院深造，博士毕业后到普林斯顿大学工作。他成为著名的计算机科学家起源于一个十分偶然的机会。他学习的是电器工程专业，对计算机科学原本没有多少知识。原打算到一所西海岸大学教授电器工程方面的课程。毕业前夕，有一次路过导师的办公室门口，当时普林斯顿大学的麦克卢斯基正为筹建”数字需要实验室“给霍普克洛夫斯特的老师打电话让推荐博士，他的老师一眼瞥见了他，觉得勤奋好学、悟性又高的得意门生正是值得推荐的人才，就把他叫进来并把话筒递给他，经过交谈与考察，他接受了普林斯顿大学的邀请，从而改变了一生的道路。

年轻的霍普克洛夫斯特到普林斯顿之后接受的第1个任务是开设一门新课程：自动机理论，这对他来说是富有挑战性的，因为他之前并没有接触过这个课程。面对挑战，他虚心地请麦克卢斯基推荐关有参考资料。由于当时没有任何一所学校开设过自动机理论的课程，也没有一本书籍，到底应该讲什么心里也没有底。通过大量翻阅文献，他开设了包括图灵、麦柯劳赫和皮孜、拉宾和斯科特、巴克斯和诺尔、哈特马尼斯和斯特恩斯以及乔姆斯基所写的6篇论文课程。他对图灵的计算模型，麦柯劳赫和皮孜的神经网络，拉宾和斯科特的有限自动机，巴克斯和诺尔描述程序的BNF，乔姆斯基的上下文无关文法等进行了深入专研与消化，并加以分析、综合和比较，逐渐理出了头绪，成功地开出了新课。后来与厄尔曼合作编写了《形式语言及其与自动机的关系》，感兴趣的同学可以作为参考书阅读。１９７０年霍普克洛夫斯特和陶尔扬合作提出了深度优先算法等一些图论中的难题而获图灵奖。陶尔扬1948年生于加利福尼亚，从小就是一个富于幻想、追求新鲜事物的人，幼年梦想成为登上火星的人，小学7年级开始看《科学美国人》杂志。1964年，陶尔扬参加了一个中学生夏令营，第一次接触了计算机，立即被神奇的计算机所吸引，因此他上加州理工学院时，辅修了学校开设的所有计算机课程，1969年毕业后进入斯坦福大学师从于著名的计算机科学家克纳斯(Knuth，1974年图灵奖得主)，1970年在克纳斯的有意安排下与康乃尔大学到普林斯顿学术休假的霍普克洛夫斯特共同研究图论的算法。这个课题实际上是”人工智能之父“麦卡锡的建议下进行的，霍普克洛夫斯特的新思路