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)构想出来的。非确定性计算机与字面意思不大一样。从字面上看,它的意思似乎是计算机随机工作,或是遵循某种不大确切的“算法”(或者一台有自由意志的计算机)。
1701742393
1701742394
我们可以这样设想一台非确定性计算机的操作:我们的计算机不止一台,我们有很多台计算机,计算机的数量有可能是无穷多的。每一台计算机被分配了某个问题的一个可能解,以负责检验这个解。
1701742395
1701742396
例如,我们的问题是,要在迷宫中找一条路线,全体计算机(在这个例子中是机器人)从入口处出发。每当这支机器人搜索队走到迷宫的一个岔路口时,他们兵分数路,每条路分配一队人马。搜索队在每个新的岔路口不停地分派人马,直到把所有可能路线探索完毕。
1701742397
1701742398
至少有一个机器人实际上从入口走到了终点。现在我们集中考虑这个机器人。它用了多长时间?很可能没用多少时间。迷宫的解通常较短,迷宫的难度在于尝试所有错误的路径以及退回到出发点的过程。一台非确定性计算机用来“解”一个问题所需的时间就是用来检验一个猜出来的解的时间。
1701742399
1701742400
NP问题大致相当于科学探索所面对的问题。当科学家试图建立新的真理时,他的地位很像上文提到的先知。科学最关心的假说与NP问题的答案类似:这些假说可以非常容易地被证实或反驳。
1701742401
1701742402
在NP问题和科学之间还有更惊人的联系——逻辑演绎本身就是一个NP问题。
1701742403
1701742405
最难的问题
1701742406
1701742407
在NP类问题中,哪个问题最难?1971年,斯蒂芬·库克证明,“可满足性”和NP中的任何一个问题相比至少同样难。他的证明显示,在NP中不存在更难的问题,因为所有NP问题都可以转化为可满足性问题。
1701742408
1701742409
随之而来的是理查德·卡普的发现(1972):许多不同种类的难题都属于可满足性问题。这些形态各异的问题来自图论、逻辑学、数学游戏、数论、密码学、计算机编程等领域,它们都和可满足性问题同样难。由最难的NP问题构成的类称为“NP完全”。用维恩图(Venn Diagram)表示,NP完全在NP的圆圈内,但位于P外。
1701742410
1701742411
严格地说,NP完全是一个不稳定的区域,也许并不真正存在。我们尚未证明NP完全问题无法在多项式时间内解决。我们的证据仅仅是经验性的:理论家和计算机程序员倾注多年的心血,试图在多项式时间内解决NP问题,但是毫无例外地失败了。在实际中,一旦证明一个问题属于NP完全,则可以认为有充分理由证明,这个问题不存在高效率的解决方法。
1701742412
1701742413
我们还可以勉强设想,存在一种尚未发现的超级算法,可以在多项式时间内解决所有的NP问题。如果确实有这种算法,那么P、NP和NP完全就全变成一回事儿了,我们可以把它们合在一起表示为一个圆圈。
1701742414
1701742415
如果存在一种高效率的解法——一个神奇的窍门,那么我们从逻辑前提中可以推出的东西 (像福尔摩斯那样)实际上就没有任何限制。反过来说,如果可满足性问题和NP完全问题没有高效率的解法,在现实中就一定存在大量的永远不会被发现的真理。我们强烈地感到,这样一种解法是不存在的。所有人都像华生医生那样,错过了大量可见的线索。
1701742416
1701742417
这意味着,对于哪些逻辑问题是可解决的,存在着一个关于其规模的相对严格的限制。在迷宫问题中,一旦迷宫规模超过一定限度,就变成实际不可解的了;同样的道理,一旦一个逻辑问题超过一定的复杂程度,也会变成实际不可解的。一个明显的推论是,我们关于实在世界的推理也是有限度的。
1701742418
[
上一页 ]
[ :1.701742369e+09 ]
[
下一页 ]