阿基米德的报复-第15部分
按键盘上方向键 ← 或 → 可快速上下翻页，按键盘上的 Enter 键可回到本书目录页，按键盘上方向键 ↑ 可回到本页顶部！
————未阅读完？加入书签已便下次继续阅读！
槐嫒先蓟ハ嗳鲜抖扇禾宓�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表示非决定性的多项式，而plete一词则意味着这些问题是该类问题中最难的。
第十章 计算机——未来的象棋之王到此为止，我们所注意的大部分是计算机科学中的理论问题，计算机和人在原则上能进行哪些类型的计算。我们已经讨论的限制都是无条件的。如果综合性理论学家能够证明他们的推测是真实的，那么旅行推销员问题就不可能找到有效的解法。这既不是因为数学家的问题，也不是计算机缺少适当的运算工具；而是根本没有这种工具，将来也决不会有。
大多数的数学家和计算机科学家都不会遇到理论上难以超越的限制。他们所面临的障碍都是自我设置的，而且都是可以超越的，至少在原理上是可以超越的。一个主要的障碍——在数学之外的许多工作中也很突出——就是这样一种倾向：稳妥的做法是照搬被普遍接受的他人的解题方法，即使这些方法不是那么圆满。那些想靠自己的努力取得成就的人，最好一下子就能搞出名堂来，否则就会招来他人的嘲笑。本章内，让我们看看汉斯。伯利纳的开拓性工作，他制造了一台能够下好国际象棋的计算机。下一章，我们则将探讨W。丹尼尔。希利斯的工作，他试图用他自己的改革性设计取代曾很好地为电子计算机服务了40年的基本体系结构。
汉斯。伯利纳是美国匹兹堡市卡内基…梅隆大学计算机学科的研究人员，他本人态度文雅，还很想跻身于世界佼佼者行列。他曾经有过这样的荣誉，现在也想为他的计算机成果赢得同样的荣誉。1968年，他曾以42步一盘棋的卓越成绩击败了苏联足智多谋的国际象棋策略家J。埃斯特林，成为国际象棋通信比赛的世界冠军，为此他曾扑在棋盘上琢磨战术整整500小时。1979年，他又设计了称为BKG（15子棋）9。8的计算机程序，并在蒙特卡洛城举行的大做广告的15子棋①比赛中，以7－1的压倒比分击败了世界15子棋冠军意大利的卢吉。维拉。伯利纳也和他自豪的父亲一样，他很高兴，BKG9。8程序已成为第一台能在任何棋盘上或纸牌游戏比赛中击败人类世界冠军的机器。
现在，BKG9。8程序已被搁置起来，世界15子棋联合会已禁止在正式比赛中应用计算机，但是，由伯利纳和他的研究生卡尔。埃贝林设计的一种称为Hitech（高科技）的新计算机程序却在另一种棋盘竞赛场所中保持了计算机的荣誉。1985年10月，Hitech程序赢得了北美计算机国标象棋的冠军称号。这项成功与其他一连串击败人类天才的胜利一起，完全证明了Hitech程序在下国际象棋方面优于任何其他计算机，也优于参加美国国际象棋协会认可的各种比赛的30，000名高明棋手（“思维”人）的99％。
现在，伯利纳已注视着弗雷德金奖金，这项10万美元的奖金将给能击败人类世界冠军的第一台计算机的设计师。Hitech程序目前要击败人类世界冠军力量尚不足。但就伯利纳的顽强性格、教育情况与比赛纪录来看，其程序的前途是不可低估的。
若按年月顺序来看，伯利纳早先热爱国际象棋，而后才爱他的计算机。他1929年出生于德国， 8岁时随父母迁居美国，定居在首都华盛顿。他发现那里的学校的要求比德国松得多，因此他寻求课堂外的挑战。在1942年的夏令营时，他看到了一些年轻人在下国际象棋，就向他们请教比赛规则。伯利纳回忆说：“甚至就在第一天，已有些棋手成为我的手下败将，情况就是这样。我从此着了迷。”
两年以后，他是他所在地区国际象棋俱乐部的冠军，并且保住华盛顿地区最佳国际象棋俱乐部冠军的称号。伯利纳说道：“我父母从不鼓励我。他们警告我说，如果我把时间都花在下棋上，我将没有什么前途。如果没有人告诉我，谁知道我将成为什么样的人？”不过在短期内，伯利纳未控制自己的棋瘾。到了1949年，他终于赢得了人人盼望的华盛顿市国际象棋冠军称号，那时他刚刚20岁，这是个破纪录的年龄。
同年，美国数学家克劳德。香农发表了一篇颇有影响的论文，他在论文中概括地论述了如何编制计算机下国际象棋的程序。当时电子计算机刚刚问世，但是，下国际象棋已被作为在新生的人工智能领域中的一个重要的目标。它与其他智力游戏不同，国际象棋引起人们的兴趣是因为在控制的条件下，通过让计算机与人类选手对阵就可以精确判断出计算机在国际象棋上的能力。参加比赛的棋手都有数字的等级，这是根据他们与其他等级对手比赛时的成绩如何而定的。计算机也要取得等级，以反映它与人
![(武侠同人)[系统+陆酗]喵的报恩封面](http://www.baxi2.com/cover/22/22818.jpg)
