1701742144
1701742145
[1]在一间屋子里同步运行圆周率机和汤姆森灯，屋子里没有其他光源，在闪烁的灯光的照明下可以见到圆周率的所有奇数位数字。
1701742146
1701742147
[2]这是一个等比数列，首项为100，公比为1/10，因此前n项之和为100（1–1/10n）/（1–1/10），当n趋于无穷时，结果即为111又1/9。——译者注
1701742148
1701742149
[3]美杜莎为希腊神话中的女妖，任何人看她一眼都会变成石头。美杜莎是不能看的，所以“弊一眼”美杜莎是不可能的，作者以此类比“超级任务”，说明超级任务是不可能完成的。——译者注
1701742150
1701742151
[4]原著此处有笔误，译文已更正。——译者注
1701742152
1701742153
[5]原文为“整数”，应为笔误。——译者注
1701742154
1701742155
1701742156
1701742157
1701742159
推理的迷宫：悖论、谜题及知识的脆弱性 第9章 NP完全：彭睢迷宫
1701742160
1701742161
豪尔赫·路易斯·博尔赫斯的小说《小径分岔的花园》描述了一个迷宫，这个迷宫极其复杂，没有人可以走出来。故事的讲述者说到他知道道路的方向，然后就开始跑题了：
1701742162
1701742163
指示说一直向左拐，这让我想起，走迷宫的一般方法就是如此，用这种方法可以发现一个确定的迷宫的中心点。我对迷宫有研究。我是彭睢的曾孙，这可非同寻常。彭睢曾经管辖云南省，后来辞职，专心写一部小说，这部小说本可能比《红楼梦》更著名。同时他还在建造一座迷宫，任何进入迷宫的人都会迷路。他花了13年时间做这两件没什么关联的事，直到一个陌生人把他谋杀了。他的小说看起来语无伦次，他的迷宫也消失了。我在英国的树下思索着关于这座消失的迷宫的一切：我想象这座迷宫是至高无上的完美巅峰；我想象它消失在稻田下或水底；我想象它是无限的，不是由八角形的亭子和往复的路径构成，而是由河流、省份和王国构成……我构想的是迷宫的迷宫，一个错综复杂的迷宫，它涵盖过去和未来，并且以某种方式把星辰包括进去。
1701742164
1701742165
“迷宫”这个词起源甚早，而且含义不固定。在古希腊罗马时期，迷宫是一种建筑，至少有一部分建在地下，故意设计得令人晕头转向。希罗多德（Herodotus）认为，鳄城附近的埃及迷宫（建成于公元前1795年）是一个比金字塔还伟大的奇观。这座迷宫包括3 000个房间，其中一半建在地上、一半建在地下，迷宫里的柱子像森林一样茂密，一直延伸到人们视力所及的范围之外。希罗多德游历了地上的一半迷宫，但是未被获准观赏地下部分。他被告知，神鳄在地下守护着法老的墓穴。许多古代作家记录了这座迷宫的逐渐衰落，它的遗址始终没有消失。1888年人们发掘了它的地基，面积是800 000平方英尺（800×1 000）。
1701742166
1701742167
在西方文化中，最著名的迷宫是古希腊克里特岛上的弥诺陶迷宫。在希腊神话中，弥诺陶是一头牛首人身的怪兽，居住在一个巨大的迷宫中央，这座迷宫是代达罗斯为克里特国王迈诺斯设计的。在克里特打败雅典之后，迈诺斯国王下令，雅典人每9年向弥诺陶进贡7名童男和7名童女作为祭品。这些进入弥诺陶迷宫的人无一生还。雅典王子特修斯自愿作为祭品进入迷宫。迈诺斯的女儿阿里阿德涅告诉特修斯，进入迷宫时沿路拉开丝线，这样就能找到出路。特修斯用这个办法杀死了弥诺陶，终止了进贡。
1701742168
1701742169
这个神话故事也许是根据雅典进贡者的传说演化而来的。在克里特人的制海权处于巅峰时，雅典派人向克里特进贡。也许他们在克里特见到了一些他们不理解的东西（莫非是一个戴着牛头面具的神秘教派的祭司？），而后他们的故事逐渐变味儿了。我们不知道古代克里特的迷宫是什么样的，我们甚至不知道它是否真的存在。在克里特语中，“迷宫”可以指迷宫一样的建筑，岩洞或者曲折的山洞（克里特地形以岩洞为特色），或者在推理中导致的不可解的困境——即悖论。在克里特文明衰落以后，克诺索斯宫殿遗址被称为“迷宫”，也许只是为了讽刺性地把它比作岩洞。残存的克诺索斯钱币显示，他们有一个建造迷宫的规划，它似乎是一个人工建造的迷宫，不仅仅是天然的岩洞。20世纪初，考古学家在克诺索斯发现了宫殿残骸，但是没有发现什么与迷宫相似的地方。
1701742170
1701742171
另一个隐藏在传说中的迷宫是罗莎蒙德的闺房（Rosamond Bower）。据推测，它建于12世纪的英国伍德斯托克（Woodstock）的一个公园里。国王亨利二世把自己的情妇罗莎蒙德夫人（Rosamond the Fair，约1140~约1176年）藏匿于这个非常玄妙的迷宫中，以免妻子阿基坦的埃莉诺（Eleanor of Aquitaine）发现。亨利二世利用一个秘密的“窍门”找到正确的路线，到达幽会地点。根据传说，埃莉诺也找到了一个“窍门”：她沿着一根丝线追踪，也到达了迷宫的中心，令罗莎蒙德饮鸩自尽。这个故事是编造的，在14世纪以前尚未出现。罗莎蒙德的闺房是否真的存在，以现代的眼光看它是否称得上迷宫，这些问题都很难说。不那么浪漫的历史学家猜测，它不过是一座设计简陋的房子，外面有一些迷惑人的通道。
1701742172
1701742173
现代迷宫差不多都是花园迷宫，通道两侧用角树（在英国常见）或紫杉制成篱笆封死。都铎王朝时期和斯图亚特王朝时期，花园迷宫在英国很兴盛。迷宫的设计者通常留出一条有记号的秘密路线通向出口，这是走迷宫的窍门。知道这个窍门，就可以毫无困难地找到出路，出入自如。
1701742174
1701742175
迷宫留下许多奥妙。走迷宫问题属于NP完全问题。它是一类普遍性的问题中的一个，有可能难倒最强大的计算机。
1701742176
1701742178
NP完全
1701742179
1701742180
世界就是一个由纵横交错的关联和关系组成的迷宫。“NP完全”（NP-Complete）这个名称客观而准确地表达了这种状态。从字面上看，“NP完全”是“非确定性多项式时间完全”（nondeterministic polynomial-time-complete）的缩写。这个令人望而生畏的术语定义了一个基本而普遍的问题种类，在哲学思辨和实际应用两方面都有重大意义。
1701742181
1701742182
NP完全问题是30年来始终困扰着计算机程序员的一类问题。计算机自问世以来，其运算速度越来越快，功能越来越强大。20世纪80年代末的计算机的运算速度大约比50年代末的计算机快3万倍。有一个炫耀的说法：“如果汽车技术的发展与计算机技术保持相同的速度，那么相当于一辆劳斯莱斯汽车应当以超音速行驶，而价格低于1美元。”然而，在20世纪60年代中期，计算机科学家开始意识到有些事不对劲。有些普通问题极难用计算机解决（也很难用已知的方法处理）。采用更强大的处理器或者投入存储空间更大的内存也无法产生可以期望的差别。这些问题逐渐被称为“难以处理的”或“内在困难的”。
1701742183
1701742184
“旅行推销员”问题即为一例。许多古老的谜题书都介绍过这个问题。这是一道数学题：一个推销员必须到达几个城市，城市之间的距离已知，要求你为一个推销员设计一条最短路线。这个问题击败了最强大的计算机。关键在于组合数学，一个本身不太大的集合产生了数量巨大的组合。解决这个问题的已知的最好办法并不比比较每一条可能路线的总英里数高明多少。随着城市数的增加，计算量如雨后春笋般激增，很快就突破了任何可以设想的计算机的计算能力。
1701742185
1701742186
NP完全作为一类问题首次在1972年的一篇论文中得到清晰的表述，论文的作者是加州大学伯克利分校的理查德·卡普。从此以后，NP完全在几十个意外的领域受到关注。小孩的谜语、谜题、游戏和脑筋急转弯中有许多NP完全问题的例子。如果找到了可高效解决NP完全问题的“解法”，那将是价值连城的发现（不过大多数计算机科学家认为不大可能找得到）。美国、苏联以及其他技术发达国家的军事安全在这个时代以NP完全为基础[1]，而这个基础并不牢靠，在信息时代，再没有什么比这更令人如芒在背了。超级大国的敏感数据是用“公开密钥”密码保护的，这种密码以大型的、实际不可解的NP完全问题为基础。类似的密码为商业私人数据和政府数据库提供安全保障。许多种类各异的问题实际上是相互等同的，这个发现在哲学上也是发人深省的。毫无疑问，“很少有技术术语像‘NP完全’这样快速地声名远播”——麦克尔·R·加里（Michael R.Garey）和大卫·S·约翰逊（David S. Johnson）影响广泛的著作《计算机与难以驾驭性：NP完全理论导论》（1979）就以这句话开篇。
1701742187
1701742188
“NP完全”是一个非常难以理解的抽象说法。我们最好用具体的例子解释一下。迷宫不仅可以用来比喻我们对知识的探求，在方法论上，迷宫还等价于我们的逻辑方法（从一个适当的、抽象的视角看）。迷宫预示了演绎方法中的核心问题——悖论发现问题。
1701742189
1701742191
迷宫算法
1701742192
1701742193
我们以这个问题开始对NP完全的探讨：是否存在解迷宫的一般方法？
[
上一页 ]
[ :1.701742144e+09 ]
[
下一页 ]