1、西北大学计算机科学系软件工程研究所1本报告的目的。n最近七大世纪难题之一的庞加莱猜想获得证明，引发了人们对解决世纪难题的兴趣。n在美国克莱数学研究所2000年提出的，每个悬赏100万美元大奖的七大世纪难题中，有一个计算机科学问题，这就是“P=NP？”问题。n 现在就要求很多同学们去研究和解决这个难题，显然是不现实的。但是作为一个从事计算机专业的学生应当知道、了解和关注这个世纪难题的解决，这就是本报告的目的。西北大学计算机科学系软件工程研究所2提纲n庞加莱猜想最后得到证明。n克莱数学研究所 七大世纪难题。n七大世纪难题之一：P 与 NP 问题。n问题涉及的几个基本概念n命题逻辑的可满足性问题n图
2、论中的一些问题nP 同构的概念n多项式界限的谓词分层n试图证明的线索和方向西北大学计算机科学系软件工程研究所3庞加莱猜想证明“最后封顶”。n哈佛大学教授、著名数学家丘成丘成桐桐教授6月3日在中国科学院晨兴数学研究中心宣布，七大世纪数学难题”之一的庞加莱猜想，近日被中国科学家中山大学朱朱熹平熹平教授和旅美数学家、清华大学讲席教授曹怀东曹怀东完成“最后封顶”工作，给出了完全证明。西北大学计算机科学系软件工程研究所4庞加莱猜想（Poincare Conjecture）n亨利庞加莱（Henri Poincar）在1904年发表的一组论文中提出：n任一单连通的、封闭的三维流形与三维球面同胚。every
3、simply connected closed 3-manifold is homeomorphic to the 3-sphere法国数学家（18541912)西北大学计算机科学系软件工程研究所5庞加莱猜想（Poincare Conjecture）n简单来说就是：每一个没有破洞的(单连通的)封闭三维曲面，都拓扑等价于三维的球面。n单连通要求所有曲面上的封闭曲线都可以收缩成一点，n以二位流型解释，例如轮胎面不是。西北大学计算机科学系软件工程研究所6亏格1亏格4亏格2亏格0曲面的亏格n曲面的亏格是环柄的数目西北大学计算机科学系软件工程研究所7西北大学计算机科学系软件工程研究所8庞加莱猜想的证明
4、n1960年美国数学家斯梅尔(S.Smale)跨过这个极难的维数,进而推广到n3维.并证明了五维及五维以上的庞加莱猜想,因此荣获1966年菲尔兹奖.n1982年,美国数学家弗里德曼(M.Freedman)证明了4维庞加莱猜想,为此他荣获了1986年菲尔兹奖.n1972年，丘成桐和李伟光合作，发展出了一套用非线性微分方程的方法研究几何结构的理论。汉密尔顿研究Ricci流，1993年在丘工作的基础上，发表了一篇关于理解奇点的重要论文。n2002年11月俄罗斯数学家格里高里.佩雷尔曼(Grigory Perelman)发表他的证明，此后他陆续将一系列的研究报告发表在国际著名的数学网站上。目前国际数学
5、界众多专家都已经注意到他的研究成果，西北大学计算机科学系软件工程研究所9庞加莱猜想的证明（续1）n从去年9月底至今年3月，朱熹平和曹怀东应邀前往哈佛大学，以每星期3小时的时间连续20多个星期向包括哈佛大学数学系主任在内的5位数学家进行讲解，回答问题。在美国出版的亚洲数学期刊6月号以专刊的方式，刊载了长达300多页的长篇论文。n2006年6月3日，丘成桐教授日在中国科学院晨兴数学研究中心宣布，中国科学家朱熹平教授和曹怀东教授完成“最后封顶”工作，给出了完全证明。西北大学计算机科学系软件工程研究所10旅美数学家、清华大学讲席教授曹怀东曹怀东中山大学 朱熹平朱熹平教授西北大学计算机科学系软件工程研究
6、所11佩雷尔曼获得费尔兹奖n庞卡赫猜想日前已经正式确认由俄国天才数正式确认由俄国天才数学家佩雷尔曼所破解学家佩雷尔曼所破解。因为这项成就，佩雷尔曼获得有数学界诺贝尔奖之称的费尔兹奖。n但当国际数学联盟试图与佩雷尔曼联络时，佩雷尔曼不但拒绝出席，而且还消失无踪。这项奖定在8.22于西班牙马德里举行的年会上颁发，得奖人拒绝现身，使大会出现有奖无得主的尴尬场面。西北大学计算机科学系软件工程研究所12Grigori Perelman refused the Fields Medal.Grigori Perelman,from Russia,who was awarded with a prestigi
7、ous Fields Medal at the International Congress of Mathematicians in Madrid,Tuesday,Aug.22,2006，but he refused the award.西北大学计算机科学系软件工程研究所13n John Ball,president of the International Mathematical Union,said that he had urged Perelman to accept the medal,but Perelman said he felt isolated from the mat
8、hematics community and does not want to be seen as its figurehead.n I regret that Dr.Perelman has declined to accept the medal,Ball said.n Perelmans work is still under review,but no one has found any serious flaw in it,the math union said in a statement.西北大学计算机科学系软件工程研究所14争论：3个小组中的每一个都对检验佩雷尔曼的工作做出了
9、重要的贡献？n汉密尔顿的评价:“曹怀东与朱熹平最近在佩雷尔曼等的工作基础上，给出了猜想证明的一个完整与详细的描述。我很高兴这两位Ricci流领域里的杰出学者所写的这篇文章。他们引入了自己的新思想，使得证明变得更容易理解。”n5月25日，密歇根大学的布鲁斯克莱纳(Bruce Kleine)和约翰洛特(John Lott)，把名为“佩雷尔曼论文注记”(Notes on Perelmans Papers)的192页文章放到了arXiv网站上。n2006年5月，摩根和田刚合作完成的书稿提交给了克雷数学研究所，并在7月25日把这本473页的书放到了arXiv网站上西北大学计算机科学系软件工程研究所15澳
10、洲华裔陶哲轩陶哲轩获菲尔兹奖 n继数学家丘成桐后，成为第二位获得此数学最高荣誉的华人。n1975年生于澳洲，是数学神童，21岁即于普林斯顿大学获博士学位，24岁成为美国加州大学洛杉矶分校教授。n由于他对偏微分方程、组合数学、混合分析和堆垒素数论有莫大贡献。西北大学计算机科学系软件工程研究所16克莱数学研究所与七大世纪难题。n美国麻省剑桥克莱数学研究所(The Clay Mathematics Institute of Cambridge,Massachusetts(CMI)n2000年5月24日在巴黎法兰西学院宣布，该机构设立了七个被称为“千僖年数学难题”巨奖，为每道难题悬赏奖金一百万美元。n
11、一百年前 1900 年 8月，David Hilbert在巴黎第二届 国际数学大会上的著名报告中提出了当时未解决的 23 个世界难题。例如Hilbert 第十问题。西北大学计算机科学系软件工程研究所17七大世纪难题。nBirch and Swinnerton-Dyer Conjecture 贝赫和斯维讷通戴尔猜想。nHodge Conjecture 霍奇猜想；nNavier-Stokes Equations 纳维叶斯托克斯方程的存在性与光滑性；nP vs NP P 与与 NP 的关系问题；的关系问题；nPoincar Conjecture 庞加莱猜想；庞加莱猜想；nRiemann Hypoth
12、esis 黎曼假设；nYang-Mills Theory 杨米尔斯理论；西北大学计算机科学系软件工程研究所18世纪难题之一：P 与 NP 关系问题。n即在多项式时间界限下，确定的图灵机器和非确定的图灵机器所接受的语言类是否相同的问题。n问题涉及的几个概念。n图灵机器(Turing Machine)和 非确定（nondeterministic）图灵机。n多项式函数时间。n图灵机器所接受的语言类西北大学计算机科学系软件工程研究所19阿伦图灵（Alan Turing）n图灵出生于1912年，1930年入剑桥大学学习数学，1934年他22岁时，在国王学院(Kings College)完成了学位论文。n
13、他的1936年的论文：论可计算数及其在不可判定问题中的应用，证明了数学不可能用计算机完全建模。n他在论文中提出的后来称之为图灵机器的概念，成为电子计算机诞生的理论基础。西北大学计算机科学系软件工程研究所20图灵机器(Turing Machine)。n符号表：s1,sn,输入符号表 ,b-n状态表Q：q1,qm,q0,qa Qn一条两个方向都是潜在无穷长的由格子组成的带子。n一个读写头，可以读所指格子上的符号，并按下述规则根据所指的符号和读头的状态做动作：在所指格子上写一符号，读头变换状态，读头位置保持不动(H)，左移(L)或右移(R)一格。n一组形如下式的规则：nsi,qj sk,ql,d.其
14、中 d=H,L或R.西北大学计算机科学系软件工程研究所21M 接收的字和语言n我们说M 接受字 w，如果把字w 放在 M 的带子上，以开始状态 q0 运行，最后在终止状态qa 结束计算。n也就是说，如果 M 在其他状态 结束计算，或计算不终止，则M不 接受字 w。n字母表上的被M 接收的语言，记作 L(M),定义为：L(M)=w *.|M 接受字 w 西北大学计算机科学系软件工程研究所22非确定的图灵机(Turing Machine)。n符号表、状态表、潜在无穷长的带子以及读写头都与确定的图灵机相同，不同的是：n它的规则形如下式：si,qj sk1,ql1,d1|skk,qlk,dkn在非确定
15、的图灵机的执行中，每一步后的状态是非确定的，有多种可能。西北大学计算机科学系软件工程研究所23多项式时间运行n用 tM(w)表示 M 在输入字 w 上的计算步数.如果计算不停机，则 tM(w)=.n用 TM(n)表示 M 对所有长度等于n（n N）的输入字的最坏的计算时间，即 T M(n)=max t M(w)|w n 其中 n 是 上长度等于 n 的字，n如果有 k 使得对于所有的 n,TM(n)nk.我们称M 以多项式时间运行（M runs in polynomial time。）西北大学计算机科学系软件工程研究所24西北大学计算机科学系软件工程研究所25西北大学计算机科学系软件工程研究所
16、26N上函数的序nN上函数 如果存在充分大的 k，使得对于所有的 nk，均有 f(n)g(n)则称 g f c c1x+c0 c2x2+c1x+c0 cnxn+co x(n+1)2n西北大学计算机科学系软件工程研究所27可计算性和实际可行性(feasible)n由三十年代发展起来的图灵机器理论、递归函数理论等为“可计算”这个概念给出了一个确切的数学定义，n“多项式时间有界的图灵机器”刻划了“实际可行的(feasible)算法”直观概念。Feasibility Thesis:A natural problem has a feasible algorithm iff it has a polyn
17、omial-time algorithm.n“P=NP?”问题：“在多项式时间界限下，确定的和非确定的图灵机器是否具有同等的功能？”西北大学计算机科学系软件工程研究所28有些确定的和非确定的机器的功能相同如果不加多项式时间的限制，n确定的和非确定的图灵机的功能是相同的，它们所接受的语言都是递归可枚举集。n对于有穷自动机来讲也是相同的，它们所接受的语言都是正则集合。n如果对图灵机加上空间的限制，n在多项式空间界限下，确定的和非确定的图灵机也具有同样的功能。西北大学计算机科学系软件工程研究所29有些确定的和非确定的机器功能不同。n并不是在所有情况下，确定的和非确定的机器都具有同样的功能。n例如，对
18、具有一个下推存贮的有穷机器来讲两者的功能是不相同的，n非确定性的下推自动机所接受的语言是上下文无关语言，n而确定的下推自动机所接受的语言却是上下文无关语言的一个真正的子类。西北大学计算机科学系软件工程研究所30“P=NP?”问题的回答有两种可能n“P=NP?”问题：“在多项式时间界限下，确定的和非确定的图灵机器是否具有同等的功能？”n回答有两种可能，一种是肯定的回答，一种是否定的回答。这两个方面都有人在作努力，比较多的人倾向于后一种回答。n这个问题的提法相当清晰，但是要解答这个问题却不容易。当代很多有名的计算机科学家都研究了这个问题，问题至今仍未解决，而且愈来愈觉得是相当困难的。解决这个问题似
19、乎需要在方法上有重大突破西北大学计算机科学系软件工程研究所31上世纪70年代有重大突破-NP完全问题nS.A.Cook(1971)1和R.M.Katp(1972)2首先提出了P归结的概念，证明了任何多项式界限下非确定图灵机器接受的语言都可以P归结为命题逻辑公式的可满足性问题。n也就是说命题逻辑公式的可满足性问题是NP完全的。西北大学计算机科学系软件工程研究所32P 归结n定义（定义（P 归结）:假定 L1，L2 分别是 1和2上的语言。如果存在一个多项是时间可计算函数 f:1*2*，使得对所有 x 1*，有 x L1 当且仅当 f(x)L2，则称语言L1 可以P 归结归结为语言L2，n定理定理
20、 设语言L1 可以P 归结为语言L2。如果L2 P 则 L1 P L1 L2f(L1)西北大学计算机科学系软件工程研究所33NP完全的定义n定义定义 我们称L0是NP完全的，如果满足条件：（1）L0 NP（2）对于NP中的任何语言L，L都可以P归结为语言L0。nS.A.Cook证明了命题逻辑公式的可满足性问题是NP完全的。西北大学计算机科学系软件工程研究所34NP完全概念的主要意义n定理定理.令L0是NP 完全的，如果 L0 P，则所有属于NP 的语言L都属于P。从而P=NP，如果能证明 L0 不属于P，则PNP。n这就是NP完全概念的主要意义。即把一个一般的 P=NP 问题归结为一个具体的语
21、言L0是否属于P 的问题。西北大学计算机科学系软件工程研究所35NP完全问题n后来证明了一大批问题都是 NP 完全问题。n命题逻辑的可满足性问题。n无向图的团集问题、离集问题和结点复盖问题。n集合族的粘连问题，隔衬问题和集合复盖问题。n有向图的环路边集问题和环路点集问题 nH 环路问题和销售员问题，n Minesweeper 西北大学计算机科学系软件工程研究所36命题逻辑的可满足性问题和重言式问题n所谓命题逻辑的可满足性问题，是说任意给一命题逻辑公式(布尔表达式)，问此公式是否是可满足的。即问对此公式的变元是否至少存在着一组赋值，而使此公式取真值。)()(32141231yyyyyyyyS)(
22、4231431321yyyyyyyyyyS西北大学计算机科学系软件工程研究所37命题逻辑的可满足性问题n在对变元进行编码以后。可以把布尔表达式变成某给定字母表中的字，而所有表示可满足的布尔表达式的字的集合可以看作是此给定字母表上的一个语言L0n定理定理.命题逻辑的可满足性问题是NP完全的(Cook)。n定理定理.CNF（合取范式）型的布尔表达式的可满足性问题是NP完全的。西北大学计算机科学系软件工程研究所383CNF(3-合取范式)的可满足性问题n定义定义.如果CNF中，每个合取因子(是个析取式)中的析取项数K，则称此表达式为KCNF(K-合取范式)n我们可以证明当K3时，可满足性问题是NP完
23、全的。n定理定理.3CNF的可满足性问题是NP完全的。)()(32141231yyyyyyyyS西北大学计算机科学系软件工程研究所39重言式问题n我们注意对于一个布尔表达式，如果已化为析取范式(DNF)，则它的可满足性是很容易(在多项式时间界限内)确定的。关键在于这种DNF和CNF之间的转化一般需要指数函数的时间。n一个表达式是可满足的，当且仅当A是非重言式。若A是一个合取范式，则用对偶定理可以很快求出A的析取范式，因此很容易得出：n定理定理.析取范式的非重言式问题是NP完全的。西北大学计算机科学系软件工程研究所40图论中的一些问题：团集、离集、复盖n我们令G=是一个有穷的无向图，V是结点集，
24、E是边集。n定义定义.G 的结点集V的一个子集合，称为是一个团集团集，如果这个子集中的每对不同结点之间都有边连接。n团集问题团集问题是任意给定无向图G和正整数K，问此G中有无结点个数K的团集。n团集问题是NP完全的。西北大学计算机科学系软件工程研究所41例如G中有K=3的团集(1,2,5,1,4,5)但没有K=4的团集；而G中只有K=2的团集(2,4,1,3,3,5)但没有K=3的团集。5143251432G G西北大学计算机科学系软件工程研究所42离集问题n定义定义。G的结点集V的一个子集合称为是一个离集，如果这个子集中的每对结点之间都没有边相连接。n离集问题离集问题 是任意给定无向图G和正
25、整数K，问此G中有无结点个数K的离集。n离集问题是NP完全的。西北大学计算机科学系软件工程研究所43n图G中有K=2的离集(2,4,1,3,3,5)但没有K=3的离集，n图G中有K=3的离集(1,2,5,1,4,5)但没有K=4的离集。5143251432G G西北大学计算机科学系软件工程研究所44结点复盖问题n定义定义。G的结点集V的一个子集合称为是一个结点复盖，如果G的每个边都与此子集中某结点相连接。n结点复盖问题结点复盖问题是任意给定无向图G和正整数K，问此图有无结点个数K的结点复盖。n结点复盖问题是NP完全的。西北大学计算机科学系软件工程研究所45n图G有K=3的复盖(如1,5,3,1
26、,2,4,5,2,4)，但没有K=2的复盖，n图G有K=2的复盖(如2,3,3,4)，但无K=1的复盖。5143251432G G西北大学计算机科学系软件工程研究所46Minesweeper 挖地雷游戏nMinesweeper is NP-complete,Mathematical Intelligencer volume 22 number 4,2000,pages 9-15 NP 完全问题已经发现有上千个！西北大学计算机科学系软件工程研究所47P 同构nHartmanis 和 Berman(1976)引入了 P 同构的概念，提出了关于P 同构的必要充分条件，而且证明了这些已知的 NP 完全
27、问题全是 P 同构的。这就更本质地揭示了这些问题的内在联系。n证明了很多不同领城的问题，包括逻辑演算、图论、规划论等领域组合问题，都是同构的，这就深刻地揭示了其中的内在规律性。西北大学计算机科学系软件工程研究所48P 同构的定义n定义.语言L1 和L2 语言，称为是P 同构同构的。如果存在P 函数f:和P函数 g:，g和f互逆，而且：(由于g与f的互逆性，也可等价地写成为 )。n显然，如果L1和L2同构，则L1可以P归结为L2，L2也可以P归结为L1。*1*2*2*1*1*221)(LxfLx21)(LxLxg西北大学计算机科学系软件工程研究所49所有的NP完全问题都是同构的?nHartman
28、is和Berman证明了许多已知的NP完全问题确实是都与可满足性问题同构，这就更深刻的揭示了NP完全问题之间的本质联系。n他们推测所有的NP完全问题都是同构的，但这只是一种推测，目前仍未得到证明。n如果能证明这一点，即等于证明了PNP。n目前还不能排除这样的可能性：PNP，又存在着不同构的NP完全问题 西北大学计算机科学系软件工程研究所50多项式受囿存在量词运算n设有谓词R，多项式函数p，我们把谓词 N(x)=(y)|y|p(|x|)R(x,y)N(x)=(y)|y|p(|x|)R(x,y)称为由 R 加多项式受囿的存在量词而得到的谓词，n定理定理 谓词 N(x)NP 当且仅当有谓词 R(x,
29、y)P，有一多项式函数p(x)，使 N(x)=(y)|y|p(|x|)R(x,y)西北大学计算机科学系软件工程研究所51 NP 的另一个定义nP=NP 问题实质上是 P 谓词类关于多项式受囿存在量词运算是否关闭的问题。nNP 的另一个定义：当有谓词 R(x,y)P，和一多项式函数 p(x)，则称 N(x)=(y)|y|p(|x|)R(x,y)是 NP 谓词，即 N(x)NP 西北大学计算机科学系软件工程研究所52两个简单的例子cabcabcn我们用自然数的十进制编码n完全平方数的集合 S 属于P n复合数的集合 F 属于 NP(不知是否属于 P).F(x)=(y)|y|x|R(x,y)其中R(
30、x,y)=(1 y x)y|x 西北大学计算机科学系软件工程研究所53Kleene 的分层nS.C.Kleene曾将算术谓词按量词的形式进行分层：n若将上述形式的谓词类记作：（R是一般递归的)E0=R(x)E1，E2，E3，A0=R(x)A1，A2，A3，n可以证明，这些类都是互不相同的，而且：(EnAn)(En+1An+1)(En+1An+1),()(1yxRy),()(2121yyxRyy),y,()(2121yxRyy)y,()(11xRy),(xR西北大学计算机科学系软件工程研究所54多项式界限的谓词分层。n若将R换为P类谓词，将量词换为多项式受囿量词。上述包含关系也是成立的。但我们不
31、知道它们是否互不相同。这是一个关于多项式界限的谓词分层猜想。n而P=NP问题以及NP=AP问题只是上述分层问题的一个特殊情况（即P=E1？E1=A1？类似地还可以提出很多问题E1=E2？2=E2？)。西北大学计算机科学系软件工程研究所55多项式分层猜测n定理定理 对于多项式分层，如果 En=An 则对任何mn都有Em=Am=Enn由于问题En=An？没有最终解决，所以多项式分层现在只能是一种猜测，我们把它称为谓词的多项式分层猜测。西北大学计算机科学系软件工程研究所56试图证明的线索方向。n要证明 P=NP,只要证明一个NP问题有多项是算法，30年来，有多少科学家和工程师在这方面作过努力，都没有
32、成功。如能成功，则有重大应用，将打破现有的密码系统的基础。目前对3-SAT的最快的算法到1.5nn要证明P NP,有两个方向，一个是对角线方法，一个是求布尔线路的下界。都未取得成功。西北大学计算机科学系软件工程研究所57停机问题是非递归的对角线证明方法nH(x,y)=“T(x)对于输入 y 能停机”其中T(x)表示x 所对应的的图灵机 XnH(x,y)是非递归的证明n假定H(x,y)是递归的，则F(x)=H(x,x)也是递归的。令F=T(f)，一方面，F(x)是递归的，F对于输入 f 能停机。另一方面，F(f)=H(f,f)，F对于输入 f 不能停机。矛盾，从而H(x,y)是非递归的西北大学计
33、算机科学系软件工程研究所58H(x,y)123456789111222333444555666777888999F(x)=H(x,x)西北大学计算机科学系软件工程研究所59“悖论”（paradox）n其字面意思为“荒谬的理论或自相矛盾的话”。n从逻辑上看，悖论性的语句具有这样的特征：如果假定这个语句为真，那么会推出这个语句为假；反之，如果假定这个语句为假，又会推出这个语句为真。说它对也不是，不对也不是，真是左右为难。西北大学计算机科学系软件工程研究所60“说谎者悖论”和“说谎者循环悖论”悖论古已有之。一般认为，最早的悖论是古希腊的“说谎者悖论”。n 我正在说谎。n A说：“下面是句谎话。”B说
34、：“上面是句真话。”n 国王说：“若果你说的是假的，烧死你；若果你说的是真的，淹死你。”大臣说：“我将被烧死！”西北大学计算机科学系软件工程研究所61集合论悖论-1901年的“罗素悖论”：n 把集合分成两类，凡是不以自身作为元素的集合称为正常集，（例如，自然数集N是正常集。）凡是以自身作为元素的集合称为异常集。（例如，所有的非生物的集合是异常集。）每个集合或者为正常集或者为异常集。n设V为全体正常集所组成的集合，即 V=x：x x，那么V是不是正常集？n 如果V是正常集，由正常集的定义知 V V，又因V是全体正常集的集合，所以正常集VV，但这说明V是异常集，矛盾；反之，如果V是异常集，那么由异
35、常集的定义知 VV，由于V是全体正常集组成的集合V的元素，V又应该是正常集。矛盾。西北大学计算机科学系软件工程研究所62老子的道德经n道可道，非常道。n名可名，非常名。说它是非常道，非常名，从而避免了悖论。西北大学计算机科学系软件工程研究所63布尔线路n一个布尔线路布尔线路是一个有穷无环的有向图，其中的非输入节点(门)标注为逻辑连接词AND,OR,NOT.，输入节点标注为变量x1,.,xn,如果每个变量赋予0或1，可以按照通常布尔逻辑的规则算出线路的输出值。ORANDANDNOTNOTX1X2X3X4(X1 X2)(X3 X4)X1X2X3X41000100110101011000101011
36、0011101对此表所列的变量赋值，该布尔线路输出值为真西北大学计算机科学系软件工程研究所64布尔线路族Bnn如果有布尔线路族 Bn 和字母表0,1上的语言 L,对于所有长度等于n的字w，w L.当且仅当把w作为输入赋予Bn，线路的输出值为1。则称 Bn 计算此语言L。n不难证明，L P,则存在节点个数（尺寸）是输入变量数n 的多项式函数的布尔线路族Bn,它计算此语言。B1B2B3Bn西北大学计算机科学系软件工程研究所65布尔线路族尺寸的下界n如果对于某个NP完全问题，能证明任何计算此问题的布尔线路族Bn，它的的尺寸关于n的函数的下界是超过多项式的函数。则证明了 P NP，否则 P=NP.n至
37、今未能证明。西北大学计算机科学系软件工程研究所66三十年来问题没有重要进展。nStephen Cook The P versus NP Problem Official Problem Descriptionnhttp:/www.claymath.org/millennium/P_vs_NP/n1979 长春 计算机科学研讨会 北大吴允曾教授推荐发表。n郝克刚：NP 完全问题及有关的理论研究完全问题及有关的理论研究 计算机科学1980 年 第1期。西北大学计算机科学系软件工程研究所67结束语n庞加莱猜想获得证明，引发了人们对解决世纪难题的兴趣。n中国人参与解决世纪难题，并做出重要贡献，对我们有极大的鼓舞。n七大世纪难题中，有一个计算机科学问题，这就是“P=NP？”问题。西北大学计算机科学系软件工程研究所68结束语n现在就要求很多同学们去研究和解决这个难题，显然是不现实的。但是作为一个从事计算机专业的学生应当知道、了解和关注这个世纪难题的解决。n我们相信这个世纪难题肯定会得到解决。如果有中国学者作出贡献，就太好了。n中国的经济起飞，也必将进入新人辈出的时代。希望寄托在有志气和有作为的青年人。西北大学计算机科学系软件工程研究所69谢谢大家！http:/ 信息学院 计算机科学系 软件工程研究所
