1701742343
在所有有限的迷宫中,发现新枝的过程最终一定会结束。在某个具体的探索阶段过后,大多数新枝会指向已经去过的节点。最终,所有的枝都被走过了,终点一定已经发现。然而,在无限迷宫中,指数增长永不停息。即使终点相对较近,找到终点也会耗费大量的时间,以至于实际上难以找到。也许相距5个节点,需要花费将近一天的时间,但是实际上一旦发现了路线,走到终点只需要5分钟。搜索一个15个节点远的终点需要若干年。如果到终点的距离是45个节点,那么为了找到终点,宇宙的全部时间都不够用。
1701742344
1701742345
我们从计算机程序员的角度来看一下最长路径问题。你希望用计算机来判定,在一个比较大的迷宫中的两个点是否被某条路线连在一起。为此,你必须为计算机提供一幅迷宫“地图”。这幅地图以表格的形式列出了迷宫中的所有节点和所有的枝。节点标明数字或名字,通过明确一个枝连接哪些节点以及节点之间的距离可以确定枝。(无论采用什么计数单位,距离都用整数表示。)一个枝可能被表示为“节点16,节点49∶72英尺”。距离是游客所走的实际长度,而非直线距离。充当入口和终点的节点同样如此表示。
1701742346
1701742347
最长路径问题还需要考虑一个因素:一个特定的距离n。最长路径问题问的是,在入口和终点之间是否存在长度大于n的直接路径。如果你愿意,n可以取任意小的值,甚至是0。当n取0时,最长路径问题转化为:是否存在一条长度大于0的路径,这等价于是否存在一条连接入口和终点的任意形态的路径。
1701742348
1701742349
既然存在性问题属于NP完全问题,比它更难的无限迷宫问题至少和NP完全问题一样难。如果判定通向G点的路径是否存在这个问题的难度已经达到了实际不可解的程度,那么具体指明这样一条路径的问题更是如此。
1701742350
1701742352
迷宫先知
1701742353
1701742354
NP完全问题有一个令人惊异的属性:其答案很容易验证。设想你遇到一个先知,无论你问什么问题,这个先知都能依靠神的启示立刻给出答案。那些相信先知的全知能力的人带着问题来问先知,这些问题如此之难,以至于他们解决不了,但是先知却能立即做出回答。
1701742355
1701742356
然而,当先知试图向所有人证明自己的特异功能时,他遇到了麻烦。他的想法是,通过表明他给出的答案的正确性来证明自己确实是全知的。但有时这是不可能的。
1701742357
1701742358
人们问他的问题分两类。最常见的一类是其他人无法回答的难题:为什么存在邪恶?神存在吗?圆周率的十进制小数展开式中小数点后第10100位数字是几?实际情况是,先知的回答从各个角度来说都是正确而精准的,但是他无法证明这些答案。怀疑者对他冷嘲热讽:对于这些问题先知可以胡乱给出任意的答案,反正别人也无法揭穿他。即使是相对而言比较现实的问题(例如圆周率的第10100位的数字)也难以验证,其难度已超出了世界上最强大的计算机的处理能力。
1701742359
1701742360
为了证明他的特异功能,这个先知必须回答那些答案可以被检验的问题。人们问他的问题中也包括这种,其中某些是怀疑者提出的,提问的目的就是拆穿他。基里巴斯的首都是哪儿?622 521的平方根是多少?《小妇人》中的姐妹们叫什么名字?这只密封的箱子里装的是什么?
1701742361
1701742362
先知正确地回答了所有这些问题,而且提问者知道先知的答案是正确的。提问者知道这一点,是因为提问者本来就知道答案。问题就出在这儿。这些问题太简单了,因而不足以确切无疑地证明先知的神力。既然提问者早已通过普通的方法知道了答案,那么可以设想,先知同样可以利用普通的方法了解或发现。怀疑者会说,他的全知可能是假冒的:他不过是一个计算天才,在一些琐细的事情方面的知识非常渊博。至于最后一个问题,他采用了“测心术”——表演者在舞台上施展的不入流的骗术。
1701742363
1701742364
这两种结果都是先知的失败。如果一个问题是其他人无法回答的,怀疑者会指控他捏造;如果一个问题的答案是已知或者可知的,怀疑者会指控他假冒。为了证明自己的全知,先知需要第三类问题,其特点在于:问题很难回答,可一旦说出答案,便很容易验证。存在这样的问题吗?
1701742365
1701742366
无限迷宫问题就满足这个要求。让怀疑者在这个迷宫中选两个随机点,然后让先知在两点间确定一条路线。任何人都能轻而易举地验证答案正确与否,他们需要做的不过是沿着指定的路线走,验证一下自己是否到达正确的地点。
1701742367
1701742368
这个问题不会是另一个“简单”的问题吗?我们必须确保选定的这两个点足够远,没有人知道连接这两个点的路线,甚至没有人可以用正常方法找到一条这样的路线。算法(包括奥尔算法)的相对低效性保证了这样一对点的普遍存在。如果两个点相距20个节点,用普通方法找到一条路线需要若干个世纪。[3]另外,这个问题不会是另一个“困难”的问题吗?不会,因为我们只需20分钟就可以检验先知的答案(假定每分钟走过一个枝)。迷宫的一个解比迷宫本身容易太多了。
1701742369
1701742370
就本质而言,第三类问题与复杂性理论中的“NP类”很接近。
1701742371
1701742373
P和NP
1701742374
1701742375
一个一般性的问题不同于一个问题的若干例子。拼版游戏是一类一般性的问题;把1 500块碎片拼起来,复原成一幅荷兰风车的图案。这是拼版游戏的一个例子。
1701742376
1701742377
NP完全理论判断问题的难度不是以某些特定的例子为依据,而是以难度随问题的规模增长而增长的函数关系为依据。在拼版游戏中,问题的规模反映为碎片的数量。碎片越多,问题越难。问题的难度最好用解题所需的时间衡量。当然,所需时间依赖于你的工作效率,但是这段时间显然与你为了完成工作而必须比照、处理的碎片数目有非常大的关系。
1701742378
1701742379
拼版游戏有一些非常困难的例子,例如有一种比较新颖的玩法,所有的碎片都是一种颜色。在这种情况下,你必须随机地比较碎片,判断它们是否吻合。在这个过程的早期,你需要把每一个碎片和许许多多的碎片比较,这个阶段会令你精疲力竭。比较和匹配操作的总体步骤与碎片数量的平方成正比。因此,所需的时间可以表示为包含n2的多项式函数,其中n为碎片的数量。
1701742380
1701742381
比较而言,这个问题所需的时间还不算多。在迷宫中,用奥尔算法找到终点所需的时间更接近于2n,其中n是起点和终点之间的节点数。当n较小时,n2和2n之间差别不算巨大;随着n值的增加,多项式函数和指数函数之间出现一条巨大的鸿沟。你可以解决一个有5 000个碎片的拼版问题,但是你无法解决一个需要5 000次正确选择的迷宫问题,除非迷宫明显非常简单。
1701742382
1701742383
从复杂性理论的角度看,所谓“容易”的问题是那些可以在多项式时间内解决的一般性问题。这些问题属于P类(P代表多项式)。我们把P设想为某处的一个辽阔的国家,粗略地画在地图上,但是边界是清楚的。地图上的任何一点或者属于P,或者不属于P。当然,我们的地图不大可靠,有时候无法判断属于与否。拼版问题是一个属于P类的点,简单的算术问题也属于此类。
1701742384
1701742385
另一类问题称为“NP”,包括所有那些答案可以比较容易地被检验的问题(可以在多项式时间内验证)。如果一个问题是简单的,那么答案也是容易检验的。如果别无检验的办法,你可以把问题重解一遍,比较一下两次的答案是否一样,这样就完成了检验。因此,所有简单问题(P类)属于答案容易检验的问题(NP)。NP还包括许多P以外的问题,迷宫就是一个例子。这样看来,NP像是一个更大的国家,而P是NP内部的一个省。如果画成地图,大致如下图。外面的矩形代表所有可能的问题。NP类并不包含所有的问题。有些极端困难的问题,甚至检验其答案都是很难的。矩形中NP的圆圈以外的部分代表这类问题。
1701742386
1701742387
我们在这个背景下讨论先知的问题。第一类问题是困难的,检验也是不容易的,它们相当于NP的圆圈以外的问题。第二类问题对应于P类。第三类问题难以回答但容易检验,对应于在NP范围内但不属于P的问题。
1701742388
1701742389
1701742390
1701742391
1701742392
“NP”这个术语(“非确定性多项式时间”)涉及一种被称为“非确定性计算机”的东西。这种理想化的计算机会特别地被称为“图灵机”,这是计算机先驱艾伦·图灵(Alan turing)构想出来的。非确定性计算机与字面意思不大一样。从字面上看,它的意思似乎是计算机随机工作,或是遵循某种不大确切的“算法”(或者一台有自由意志的计算机)。
[
上一页 ]
[ :1.701742343e+09 ]
[
下一页 ]