1701742177
推理的迷宫：悖论、谜题及知识的脆弱性 [:1701739724]
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
1701742190
推理的迷宫：悖论、谜题及知识的脆弱性 [:1701739725]
1701742191
迷宫算法
1701742192
1701742193
我们以这个问题开始对NP完全的探讨：是否存在解迷宫的一般方法？
1701742194
1701742195
是的。事实上，存在好几种方法。并非所有的迷宫都需要动脑筋。单行线迷宫从头到尾都只有一条通道，没有岔道，没法走错。许多中世纪的迷宫迂回曲折但是没有岔道，唯一的通道会通向一棵树或一座神殿。早期的英国教堂墓地设计成这种类型的迷宫，象征迂回曲折的人生道路——虔信者在世间邪恶的诱惑下穿行。
1701742196
1701742197
克诺索斯的弥诺陶迷宫可能就是没有歧路的。钱币的图案显示了一条没有岔道的通道。如果你在这样一座迷宫里遭遇弥诺陶，你只需做一件事：掉过头跑。这样你永远都不会走进死胡同，另外，也许这些钱币只是表明一种设计风格，而非一张真正的地图。还有一种可能：这些图案也许展示了在更复杂的通道网络中应当怎么走。除非有岔道，否则你用不着拿一根丝线标记路线。
1701742198
1701742199
每座迷宫至少有一个入口，而且大多数迷宫都有一个终点——在迷宫中你试图到达的一个地点。终点通常在迷宫的中心附近，当然，终点也有可能只是迷宫边界上的一个出口。[2]破解迷宫的目的是找到一条路线，从入口走到终点。路线也许只有一条，也许有多条。当连接入口和终点的路线不止一条时，一个潜在的谜题是发现最短路线。
1701742200
1701742201
有些迷宫的入口不止一条。这与仅有唯一入口的迷宫并无本质不同。你的第一个选择是从哪个入口进入，这个选择是在进入迷宫以前做出的，但是这与在迷宫内选择路径没什么两样。有些迷宫有多个终点，要求游客走遍迷宫的各个部分，或者一系列由雕像、长椅或其他东西标示出来的地点中的每一个。路易十四在凡尔赛建造了一个著名迷宫，游客需要找到39座根据伊索寓言设计的雕塑。每座雕塑的原型都是伊索寓言中会说话的动物，水柱从它们的嘴里喷出来，形成喷泉。最后，还有一类迷宫是没有终点的，这种迷宫的走法就是进去闲逛，然后找条路出来。
1701742202
1701742203
在迷宫格局中，每个分岔处称为一个“节点”。节点是通道交叉的地方，在节点处你必须做出选择。入口、终点和死胡同的终端也被视为节点。两个节点之间的通道被称为一个“枝”。任何迷宫都可以用简化的图来表示，在图中，“节点”用点表示，“枝”用线表示，点和点之间用线连接。用数学术语来说，迷宫是一张“图”。
1701742204
1701742205
几乎所有物理形式的迷宫都是二维的。这意味着，枝和枝之间从不交叉。在三维迷宫中可以有天桥和地道，枝和枝可以交叠，如同高速公路的立交桥。
1701742206
1701742207
在图上解迷宫和实际走迷宫不是一回事。面对谜题书上印出来的迷宫地图，通常只利用眼睛就可以解决，人眼会自动地把迷宫当作一个“完形”。但是当你身处于一个实际的迷宫内部时，通道两侧被篱笆或石头封闭，你很难在头脑中形成一个整体图像。高明的设计者会把某些节点设计得非常相似，让你觉得自己在同一条路上兜圈子，而实际上你到达的是一个新地点。此外，在图上解迷宫可以用一些由来已久的方法，例如，把终点当作起点进行倒推（这种方法有时使问题简化，有时则更麻烦），或者勾掉所有死胡同，从而使路线变得更清晰。但是在实际的迷宫内部，这些法子都用不上。
1701742208
1701742209
迷宫的难度与各节点处发出的“枝”的数量息息相关。如果每个节点处都只有一个枝，那么这个迷宫一定是单行线迷宫。我们可以把节点想象成两颗珠子，在珠子之间有一条线，无论这条线如何盘旋环绕，一个不变的事实是，它总是连在两颗珠子之间。沙特尔教堂的迷宫就是单行线迷宫，这个迷宫没有墙，是用蓝色和白色的大理石在地板上铺出来的。
1701742210
1701742211
如果每个节点处有两个枝，迷宫同样毫无难度可言。我们可以把它设想成一堆珠子串在一条线上。走这样一个迷宫时，你不用做出选择。实际上，你通常不会把连接两个枝的连接点视为一个节点。把这两个枝看作连续的一个枝更简单，所谓的节点不过是在这个枝上打了一个结。
1701742212
1701742213
在迷宫里，一个真正的岔道至少需要几条通道汇聚在一个点（三条路形成三岔路口）。节点处汇聚的枝越多，迷宫就越难走。
1701742214
1701742215
大多数近年来的迷宫按照习惯采用了接近直线的设计，道路和限制通道的篱笆构成密密麻麻的蜂巢，填满整个区域。这使得此类迷宫比每个节点发出四个枝还要难。凡尔赛迷宫采用了更灵活的设计。各个枝不必要地平行，许多枝汇聚在一个单独的节点上。最高纪录是一个节点上汇聚了5个枝。凡尔赛迷宫的设计师安德烈·勒诺特雷（Andre Le Notre）在尚蒂伊建造了另一个迷宫，其中心节点汇聚了8个枝。
1701742216
1701742217
下表介绍了关于几个著名迷宫的统计数据。有几处，节点和枝的数目应当如何计算有待商榷。在每个场合，细心的游客需要做出决定的地点都被我算作一个节点，入口、终点和死胡同的终端也被当作节点，但是只有两个枝的冗余节点被排除在外。最后一列是平均每个节点汇聚的枝的个数，这个数量大致反映了迷宫的难度。
1701742218
1701742219
1701742220
1701742221
1701742222
凡尔赛迷宫
1701742223
1701742224
1701742225
1701742226