Science 版 (精华区)
发信人: emacs (In the Name of Love), 信区: Science
标 题: 《阿基米德的报复》第九章 威利·洛曼无辜地死去了�
发信站: 哈工大紫丁香 (2002年07月31日18:10:14 星期三), 站内信件
第九章 威利·洛曼无辜地死去了吗？
从某种基本意义上讲，计算机和数学家只是不容易识别的图灵计算机，知道
这一点也许令人泄气。但在另一方面，从表面上看过于简单的图灵计算机，由于
证明能够解各种各样的计算问题，从而又可被认为是鼓舞人心的。数学家与计算
机之间理论上的相似性不仅适用于他们能解出的各种问题，而且也适用于他们不
能解出的各种问题。 工业上每天都出现许多计算问题，若用任何已知的方法
去解，则太费时间，现在都例行地由计算机去着手解决。然而工业需要的是对这
些问题的解法，而计算机常常牵扯到程序设计人员的水平，他们往往不能编出最
佳程序。其中有许多是众所周知的使旅行推销员感到为难的问题；已知一个城市
与公路网络，要找一条推销员在往返旅程中到每个城市去一次的最短路线。仅有
一种已知的算法用来解这种旅行推销员问题，就是可靠的逐步试探法，这种方法
费力，缺乏预见性，只是对每一种可能性都进行尝试。看来，数学并未减轻威利·
洛曼的烦恼。
过去15年内，数学家们都感到迷惘，他们寻求巧妙的、较快的算法都告失败，
这是由于他们无知呢，还是这种问题本身存在内在的困难？按照当前的知识水平，
暂时还没有较快的算法，甚至在理论上也没有。目前还没有人能够证明这一点。
对证明的研究已是理论计算机科学中最为热门的课题，而且在这个领域中工作的
数学家已被公认为是复合型理论学家。
当数学家们谈到保证解题方法时，他们的意思就是指算法。不要由于“算法”
（algorithm）这个英语单词的发音令人生畏而摈弃它，它是9世纪波斯数学家阿
布·贾法尔·穆罕默德·伊本穆萨·阿尔霍瓦里米的姓氏音译转讹而来的，他的
语义遗产还包含有单词代数（algebra）在内。算法的音难读但不难懂。你早已
了解什么是算法的直观概念。
你可曾记得，在你读小学时，你的英语老师让你制定出一整套令人厌烦的规
定，去做诸如系鞋带一类枯燥无味的琐事，然后老师叫约翰尼·怀斯盖严格按照
你的规定去系他的鞋带（与此同时，这个讨厌的老师还会让你大声念你的那一套
规定）。
当然，他会立即出错——而且是个大错——因为你没有考虑一些看来好像是
理所当然不成问题的基本步骤，就像系鞋带时理所当然要握住鞋带的塑料包头，
而不是握住它的中部一样。如果你详详细细地写出，那么你就会得到一个有关系
鞋带的规则系统，而这个规则系统不过是一个循序渐进的程序，在这个程序中，
每一步都说得很明确，你可以按部就班地解决每个问题。每个步骤都要规定得清
清楚楚，其间不允许留下任何靠可能、直觉、经验、解释或想象等方法来处理的
细节。
当然，数学家们对于计算问题的算法要比系鞋带更感兴趣。两个整数相加的
算法，根据小学老师教给我们的方法，是用纸和铅笔按照如下的明确步骤进行：
把整数写成一行，一个数写在另一个数的上方，两数右端对齐，在它们下方划一
横线，从右到左地进行计算，有时还“进位”1，而且照此步骤计算许多其他数
的相加，也是不成问题的。这种算法应该包括如下法则，像“如果一个数2在另
一个数4的上方，可在其下写一个数6”和“如果一个数3在另一个数6的上方，可
在其下写一个数9”等法则。
算法的功能之一是其能用于一个问题的所有实例。例如加法算法可以算出任
何两个整数的和。你虽然花费时间去详尽写出一种算法的全部细节，但你却得到
了一种能够保证工作的方法。计算机的程序或是单一的算法或是系列的算法。如
果没有指令告诉该算法的每一步骤应该做些什么，那么计算机就同不能模拟系好
鞋带一样，也不能进行两数相加的计算。程序设计员的作用在于编好完整的指令，
换句话说，要编好完整的算法。当程序设计员责怪其程序中的错误时，他的意思
是指在编写详尽算法或把算法译成计算机语言时，他犯了一个错误。
必须强调的是，算法的用户不管是一部机器还是一个人，不需要对算法做出
判断。例如，加法算法的使用，不需要“什么是数字”这一概念。要应用算法时，
你可以盲目地按照法则进行。比方说，你不必知道，5是跟在4之后，7是大于3等
等，甚至你也不必知道你是在使用十进制的数制。哲学文献中已有许多篇幅谈论
过，就计算机的思考能力而言，缺乏判断会意味着什么。但是，探讨这样一个引
人兴趣的说法则使我们离题太远了。
数学家们都不大关心旅行推销员这一专题。对于一系列较小的城市与公路网
络，由于没有多少可能的路线需要审查，因而找到解法是很容易的。甚至对于大
的城市与公路网络，那也可能幸运地或者偶然地找到最佳的路程。当数学家们宣
称某问题实际上是不可解时，他们的意思是，仅仅知道保证解法的许多方法，就
像穷举搜索所有可能性的方法一样低效，即使对于最高级的超级计算机来说，这
种穷举搜索法也是太慢的。
数学的行家对于快速（与可用）的算法和慢速（与不可用）的算法都有严格
的确定方法。假设数字n是某问题大小的量度（对于旅行推销员问题，n是城市与
公路数目的量度）。对于快速的算法，随着计算问题规模的增大，完成算法所需
的时间的增长不会大于n（表示计算规模）的某个多项式。多项式是一种数学函
数，诸如2n（加倍）、3n（3倍）、n2（平方）、n3（立方）、3n10和64n100等。
而对于慢速的算法，例如用于解旅行推销员问题的穷举搜索法，则其执行时间将
按问题规模增加的指数增加，即2n、6n或12n等。
当n的值小时（也就是说，对于简单的问题），已知的多项式函数可以等于
甚至超过已知的指数函数，但是当n的值大时，任何指数函数都将迅速地超过任
何多项式函数。例如，当n等于2时，多项式函数n2等于4，它等于指数函数2n。
但当n等于10时，n2只等于100，而2n却会像火箭上天那样猛增到1，024。毫无疑
问，指数函数的增加会大大超过多项式函数的增加，这曾使托马斯·马尔萨斯感
到忧虑，因为他发现人类的人口是以指数函数增长的，而与之相比，食物的供应
则只以多项式函数增长。
解旅行推销员问题，仅有已知的一种方法是按指数减慢的方法，即审查所有
可能旅程的方法，这一事实意味着，在当今这个年代里，我们已不能对看来如此
简单的问题有真正的了解。综合性理论学家总想试图证明这个迷惑人的猜想：不
管我们如何努力尝试，我们对它都不会有任何了解，因为它就是不能理解的。
看来与旅行推销员问题似乎有点相似的许多问题，数学家们对它们已经有所
了解。例如，请考虑，一位公路检查员，他负责检查某段公路网，旅行推销员可
能就在这段公路网上驱车。这位检查员渴望回家去看妻子和孩子，他想知道，是
否有一条来回的路程，只须经过每条马路一次，只经过一次。但他并不关心城市，
他只是想自己能走过公路的每个路段，而且还不重复。而从另一方面来说，旅行
推销员却不关心公路，他只想去每个城市，每个城市只去一次，这样可把其汽车
里程减到最短。
伦哈德·欧拉1736年的研究工作，轻而易举地回答了公路检查员的问题。欧
拉是一位29岁的普鲁士数学奇才。原普鲁士城市柯尼斯堡（现为苏联城市加里宁
格勒）位于普雷盖尔河的两岸，并且包括克尼霍夫岛以及河流岔口中部的一块狭
长陆地。城市的4个区域由7座桥梁的网络连接起来。
据说，伊曼纽尔·坎特习惯于环绕城市进行长路程的保健散步运动，而且居
民们也都想知道，是否可能有一条进行散步的来回路线，可以穿过所有7座桥梁，
而每座桥梁只能穿过一次。由于桥梁的数目很小，这个问题可以用列举所有可能
路线的方法（否定的方法）去求解，也就是说采用类似于旅行推销员这个小问题
的、没有预见性的穷举法。
这个问题由多产数学家欧拉去解，欧拉是一位有13个孩子的父亲，同时还著
有80本书的数学研究成果。传说，许多研究报告都是在第一次与第二次叫他去吃
饭之间的30分钟时间内写出来的，他预见性地证明这种路程问题无解。数学的灵
魂大力提倡分析最普通的例子。因此，欧拉不仅想为柯尼斯堡的居民，也想为各
地喜欢桥梁散步的人们解决问题，他试图解答一个普遍性的问题：“有若干河流
及其分支穿过某一地区，并在其上架设任意数量的桥梁，已知河流与桥梁的布局，
求是否有可能在每座桥梁只穿过一次的情况下，穿过所有的桥梁。”如果你把陆
地区域看成城市，把桥梁看成公路，那么你就可以认为，这个一般性问题与公路
检查员所面临的问题相同。
为了解柯尼斯堡桥梁问题，欧拉用几何线表示每座桥梁，用几何点表示每块
陆地。
在这幅图中，欧拉已把问题简化成基本线条，去掉了所有无关紧要的内容。
比方说，线与点的表示无法区别桥梁是宽还是窄，是特定的桥梁还是连接同一陆
地区域的其他桥梁，是大块陆地还是小块陆地，乃至是岛屿还是河岸等。这些区
别也许在其他方面非常重要，但与穷举的非重复性散步方法无关。这是一种漂亮
的数学表示法：它仅需要在手边保留那些有关的情况，从而使数学家免受枝节问
题的干扰，更能集中注意力于问题本身。
欧拉已能证明，只有当点（陆地区域）为0或2，形成的线（桥梁）为奇数时，
才可以进行穿过所有桥梁的非重复散步。你只要稍加思考就可支持这一结论。如
果你穿过一座桥梁到另一处陆地去，必须还有一座桥梁让你离去，否则你将被困
在那里。大片陆地需带有偶数桥梁才能确保那里有一条进去的路，另有一条离去
的路。要是大片陆地只带有奇数的桥梁，那只有在旅程的终点（在那里你不需要
一座桥梁离去）和旅程的起点（在那里你不需要一座桥梁进去）才有可能进行非
重复的旅行。由于只有一个起点和一个终点，因此只有两处陆地才能有奇数的桥
梁。在柯尼斯堡，4处陆地区域的每一处都连接了奇数的桥梁，即使没有比较严
格的来回旅程条件，那么完全的非重复散步显然是不可能的。
欧拉关于任意数桥梁与任意数陆地区域的结论要比归纳成普通的常识重要得
多，认识到这一点很重要。我们的推论只是简要地说明，如果欧拉所断定的条件
不能够满足，则非重复的旅行将是不可能的。欧拉的结论是很强有力的，直观上
却不是很明显的：他证明了，如果这一简单条件得到满足，也就是说，当陆地区
域数为0或2，而且连接它们的桥梁数为奇数时，非重复的行程总是可能的。
要把欧拉的分析应用于一般情况，需要数出每处陆地区域的桥梁数。由于每
座桥梁都要连接两处陆地区域，因此桥梁要两倍计数。如果桥梁数为n，那么欧
拉的分析需要2n个步骤。桥梁的计数可以作为一种算法列出公式，而且它将成为
一种非常有效的算法，因为虽然问题变得越来越复杂，演算所花费的时间却仅多
了一倍。而从另一方面看，所有可能旅程的穷举搜索法则将成指数地迅速增长为
2n。
在旅行推销员问题中，对效率很低的穷举搜索法仍无简捷的方法。比方说，
你仍不能计数出连接于每条公路的城市数，并根据这些数是奇数还是偶数来做出
某种结论，或者就此而言，也不能根据这些数的其他性质得出结论。而且，这还
不仅是我们不知道寻求那些性质的问题。还有可能是这些性质本来就不存在。这
正是综合性理论学家都在努力证明的问题。
旅行推销员问题不仅仅是惟一的计算问题，许多数学家都不理解其快速算法。
还有一整套叫做NP-完全的问题，对于这类问题，人们仅知道其计算所需时间以
指数方式激增。①在NP-完全的问题中，另有一个众所周知的例子称为人群问题：
已知有一大群人，比方说，共100人，他们之间是否有许多人，比方说，有50个
人，全都彼此认识吗？
“你可以解这种问题，”美国麻省理工学院综合性理论学家迈克尔·赛普泽
说道，“先投出 100个点，每点表示一个人，然后在相应的彼此认识的两人的点
之间划一直线。”于是你将希望这组的50个点全都有连线。赛普泽接着又说：
“看起来它很像一个有关计算机方面的重大问题，然而它不是。我们知道，如何
去解这种问题，仅有的一种方法实质上是查看50人小组的所有连线，它们的数量
非常多，就像10的29次方。要解出这个问题，即使应用快速的计算机，也要好几
百年。”
旅行推销员的问题、人群问题、以及所有其他NP-完全的问题，都有难以理
解的共同特点：如果有人声称，他对于这类问题中的任何一个特殊事例已经有了
解法，那么要检验这个解法则是很容易的事。对于旅行推销员问题，只要检查所
提出的旅程，并查明是否包括了每个城市一次。对于人群的问题，则要双向检查
已被辨认全都互相认识而成群体的50个人。美国伯克利市加利福尼亚大学计算机
科学教授理查德·卡普把 NP-完全的问题比作拼图玩具：“它们可能难于组合，
但是当有人向你展示一幅完全的拼图时，你就能一下子知道问题已有正确解。”
NP-完全的问题还有一个醒目的特点，如果这类问题中的任何一个问题能够
用快速算法求解，那么其他问题也都能用此法解出。而且，对于某类NP-完全问
题采用快速算法毫不费力，而且稍加改进，就可用于解任何其他NP-完全问题。
例如，如果人们发现了一种用于解旅行推销员问题的快速算法，那么数学家们就
会自如地运用快速方法去解人群问题和所有其他的NP-完全问题。因此，旅行推
销员问题是否有快速解法与NP-完全问题是否真的像看上去那样难这一较大问题
有关。
美国电话电报公司的戴维·约翰逊说道：“我认为，现在每位数学家实际上
都认为NP-完全问题有内在的困难。”约翰逊是这一领域的权威人士，著有《计
算机和难处理性：NP-完全理论指南》一书。他还说：“真正的问题是证明它。”
这种论点动摇了一些数学家的想法，他们认为他们也许能够证明旅行推销员
问题及同类的其他问题都不会有快速解法——从来就没有过——即使未来让爱因
斯坦一类大师来绞脑汁也不会有。他们怎么会提出要证明这样的问题？
目前的工作都集中在逻辑门上，它已被认为是计算机硬件中最基本的单元。
在电子计算机内，逻辑门是一种组件，由任意数目的输入引线与一根输出引线组
成。逻辑门也是一种二进制器件：每根引线中的信号都被认为或是1、或是0。
（在电子学术语中，高电平对应于1，低电平对应于0。）
每一个逻辑门都能完成3种基本运算中的1种：“非”、“与”或“或”。这
3种运算的名称都是根据布尔代数中已经使用的词“非”、“与”和“或”而得
来的。布尔代数是19世纪40年代由乔治·布尔研究出来的一种开拓性的形式逻辑
体系。布尔是一个贫穷补鞋匠的儿子，他自学数学，研究出符号逻辑体系，其中
1表示真的，0表示假的。尽管布尔的研究工作使他获得了爱尔兰科克大学的数学
教授职位，但直到100多年后第一部电子计算机问世之后，他的逻辑体系才得到
数学界的完全赏识。
在形式逻辑中（和日常的英语中），词“非”加在前面可把真语句变成假语
句，而且反过来也一样。把它换成布尔代数的术语，则是“非”可把1转换为0，
0转换为1。因此，“非”逻辑门有一根输入引线，并把输入信号转变为其相反信
号，即如果输入是1，则输为0，而如果输入为0，则输出就为1。
当然，词“与”用于连接单个语句成为复合语句，即如果每个组元都是真的，
那么复合组元也是真的。现举一简单例子，“朱尔斯吃豆腐与吉姆吃多夫条形面
包”，只有当朱尔斯和吉姆两个人都在吃上述的食物时，它才是一个真实语句。
由于同样的理由，“与”门可接受两个或多个信号输入，如果所有的输入都是1
时，那么输出也是1，否则，则输出为0。
词“或”也是用于连接语句成为复合语句，但只要一个或几个组元都是真的，
则其复合组元也是真的。如果朱尔斯或者吉姆（或者他们两人）在吃他们各自的
食物，那么“朱尔斯吃豆腐或吉姆吃多夫条形面包”才是真语句。同样地，“或”
门可以接受两个或几个信号输入，但只要至少输入之一是1时，则其输出也是1。
布尔代数的绝妙之处在于，1和0不仅表示真的和假的，而且还可以表示任何
两种不同的状态。例如在旅行推销员问题中，0和1可以表示城市之间的相应关系：
如果两个城市由一条公路连接，则以1表示，如果它们没有公路连接，则以0表示。
在人群的问题中，1可以表示两个人成为朋友的状态（或者在该问题的图解表示
法中，表示由一条线连接的两点），0表示他们不是朋友的状态（表示没有线连
接的两点）。
在计算机中，任何数目的“与”门、“或”门和“非”门都可以连接在一起，
形成一种电路。例如下图示出4个“与”门和1个“或”门组成的一种小型电路，
它可以用来求解人群问题的普通实例：在4个人的一组中，有3个人是朋友吗？
然而，随着人群问题的人数增加，用于已知解法的电路大小（也是逻辑门的
数目）将按指数方式激增。如果数学家们能够证明，对于任何可能已知或未知解
法，电路必按指数方式增大，那么他们就能证明人群问题没有快速算法。
数学家们还不知道如何开始这样的证明，已经转而考虑另一特殊的问题，这
就是通常都有快速算法的奇偶函数，而且他们还试图以某些基本方式来限制电路，
使得快速算法不再产生作用。（奇偶函数可在一串的0与1中确定是否产生偶数或
奇数。）这种方法看来也许有些怪，其实它并不怪。数学家们对于如何证明电路
必须是大型的了解甚少，因此为此目的而做的任何证明，甚至是某种人为的情况，
也都将会有所进展，而且可以提供证明真正论点所需的数学工具。赛普泽说道：
“这是数学中的普通方法。如果问题很大，可试图把它限制到某些范围，并求解
其中一部分，希望这种分部解法使人们对原来的问题会有更深的了解。”
在这一领域内，早期的工作限制了电路的研究工作的深度，这里的深度是指
逻辑门的层次数目。1981年取得了第一批成果，当时美国卡内基-梅隆大学的赛
普泽及其两位同事证明了，如果他们限制用于奇偶函数的电路深度，那么电路宽
度的扩展快于任何多项式。1985年，美国斯坦福大学的安德鲁·姚在这方面取得
了更惊人的研究成果，他证明了电路的宽度不仅以超多项式的方式扩展，而且还
以指数的方式扩展，这表明这种问题虽然受到人为的限制，但也有内在的困难。
姚的成果很快地传遍了数学界。赛普泽这样说道：“每个人都认为这个结果
很满意，但也是非常复杂的。”姚的方法为他人铺平了道路，好几个研究人员很
快地对他的结果做了改进。美国电话电报公司贝尔实验室数学科学部主任罗纳德·
格雷厄姆说：“这很像开车的头4分钟路程，一旦有人学会它，那么人人都可以
学会它。”
1985年8月，美国麻省理工学院计算机学科研究生约翰·哈斯特德采用了姚
的基本理论，但是简化了他的论据。哈斯特德说道：“在工作过程中，我获得了
比较有力的结果。（在这种有限制的问题中）我们所知道如何设计的最小电路并
不比我在理论上曾经证明它们应有的规模大出很多。”后来的证明都表明：数学
家们实际上知道如何设计出并不比他们在理论上所推断的最佳电路差很多的电路。
对于这些有限制的问题来说，不是数学上的无知，而是问题的本身排除了快速的
解法。
苏联莫斯科大学的两位数学家阿·拉兹波洛夫和阿·安德烈耶夫在不限制电
路深度但却限制所进行的运算方面取得了很大的成功。拉兹波洛夫又证明了如果
不允许用“非”门的话，则用于人群问题的电路规模的增长将快于任何多项式的
增长。而且，数学家们还在这里对这一结果做了改进，它表明电路必须是按指数
方式增大。安德烈耶夫通过禁止用“非”门还能够证明另一类问题也需要大规模
电路。
这些成就使这一领域乐观起来，虽然还没有人知道怎样才能减少对电路的限
制并证明在无限制的情况下，旅行推销员的问题的确很难。“还有很长的路程要
走，”赛普泽这样说道，“6年以前，我曾与人打过赌，我希望他还记住，将在
2000年得出证明。我仍然信心十足，还有12年多的时间。”格雷厄姆还抱有更大
的希望：“在以后3年内得到证明也不会让我吃惊。”
尽管人们普遍乐观，但在综合性理论方面（数学的一个分支学科，它表述了
问题的难度）的研究人员，以他们的直觉已经知道他们会失败的。1985年冬天，
美国麻省理工学院的数学研究生戴维·巴林顿曾证明，计算机能够运算的某些原
始表示法会比该领域中任何人所能设想的更有功效。这种原始表示法不包含“与”
门、“或”门和“非”门，但却包含一个分支门，它也有两根输出引线。当分支
门受到触发时，如果输入信号具有一定的指定值，则分支门就会沿两根引线之一
送出一个信号；对于所有其他输入信号，分支门沿另一根引线送出一个信号。换
句话说，分支门能够处理计算机程序中的语句，诸如“如果x=5，转向步骤4；对
于所有其他x，转向步骤7”。
巴林顿又证明了，全部由门层次不超过5层的分支门构成的电路，可以解所
谓的多数问题：在一串的0和1中，1是不是多数？综合性理论学家普遍地（并且
错误地）认为分支门限制于任何固定高度，不可能求解多数问题，更不用说严苛
的五层限制了。
巴林顿说道：“我的证明很简单，但它令人惊奇，因为他们总是认为我所试
图证明的都是假的。”巴林顿的结果也许没有多少实际用途——他又说：“除了
它可以让我在一所好大学获得一个教师职位之外。”而且它还可以说服数学家们
不要在复杂的综合性理论领域中如此自信。________
① 如果你一定要知道的话，NP表示非决定性的多项式，而complete一词则
意味着这些问题是该类问题中最难的。
--
What a friend we have in EMACS,
All our text-problems to halt!
What a privilege to keypress
Control-meta-ESC-shift-alt!
※ 来源:·哈工大紫丁香 bbs.hit.edu.cn·[FROM: 天外飞仙]
Powered by KBS BBS 2.0 (http://dev.kcn.cn)
页面执行时间：210.599毫秒