豪尔赫·路易斯·博尔赫斯的小说《小径分岔的花园》描述了一个迷宫，这个迷宫极其复杂，没有人可以走出来。故事的讲述者说到他知道道路的方向，然后就开始跑题了：
指示说一直向左拐，这让我想起，走迷宫的一般方法就是如此，用这种方法可以发现一个确定的迷宫的中心点。我对迷宫有研究。我是彭睢的曾孙，这可非同寻常。彭睢曾经管辖云南省，后来辞职，专心写一部小说，这部小说本可能比《红楼梦》更著名。同时他还在建造一座迷宫，任何进入迷宫的人都会迷路。他花了13年时间做这两件没什么关联的事，直到一个陌生人把他谋杀了。他的小说看起来语无伦次，他的迷宫也消失了。我在英国的树下思索着关于这座消失的迷宫的一切：我想象这座迷宫是至高无上的完美巅峰；我想象它消失在稻田下或水底；我想象它是无限的，不是由八角形的亭子和往复的路径构成，而是由河流、省份和王国构成……我构想的是迷宫的迷宫，一个错综复杂的迷宫，它涵盖过去和未来，并且以某种方式把星辰包括进去。
“迷宫”这个词起源甚早，而且含义不固定。在古希腊罗马时期，迷宫是一种建筑，至少有一部分建在地下，故意设计得令人晕头转向。希罗多德（Herodotus）认为，鳄城附近的埃及迷宫（建成于公元前1795年）是一个比金字塔还伟大的奇观。这座迷宫包括3 000个房间，其中一半建在地上、一半建在地下，迷宫里的柱子像森林一样茂密，一直延伸到人们视力所及的范围之外。希罗多德游历了地上的一半迷宫，但是未被获准观赏地下部分。他被告知，神鳄在地下守护着法老的墓穴。许多古代作家记录了这座迷宫的逐渐衰落，它的遗址始终没有消失。1888年人们发掘了它的地基，面积是800 000平方英尺（800×1 000）。
在西方文化中，最著名的迷宫是古希腊克里特岛上的弥诺陶迷宫。在希腊神话中，弥诺陶是一头牛首人身的怪兽，居住在一个巨大的迷宫中央，这座迷宫是代达罗斯为克里特国王迈诺斯设计的。在克里特打败雅典之后，迈诺斯国王下令，雅典人每9年向弥诺陶进贡7名童男和7名童女作为祭品。这些进入弥诺陶迷宫的人无一生还。雅典王子特修斯自愿作为祭品进入迷宫。迈诺斯的女儿阿里阿德涅告诉特修斯，进入迷宫时沿路拉开丝线，这样就能找到出路。特修斯用这个办法杀死了弥诺陶，终止了进贡。
这个神话故事也许是根据雅典进贡者的传说演化而来的。在克里特人的制海权处于巅峰时，雅典派人向克里特进贡。也许他们在克里特见到了一些他们不理解的东西（莫非是一个戴着牛头面具的神秘教派的祭司？），而后他们的故事逐渐变味儿了。我们不知道古代克里特的迷宫是什么样的，我们甚至不知道它是否真的存在。在克里特语中，“迷宫”可以指迷宫一样的建筑，岩洞或者曲折的山洞（克里特地形以岩洞为特色），或者在推理中导致的不可解的困境——即悖论。在克里特文明衰落以后，克诺索斯宫殿遗址被称为“迷宫”，也许只是为了讽刺性地把它比作岩洞。残存的克诺索斯钱币显示，他们有一个建造迷宫的规划，它似乎是一个人工建造的迷宫，不仅仅是天然的岩洞。20世纪初，考古学家在克诺索斯发现了宫殿残骸，但是没有发现什么与迷宫相似的地方。
另一个隐藏在传说中的迷宫是罗莎蒙德的闺房（Rosamond Bower）。据推测，它建于12世纪的英国伍德斯托克（Woodstock）的一个公园里。国王亨利二世把自己的情妇罗莎蒙德夫人（Rosamond the Fair，约1140~约1176年）藏匿于这个非常玄妙的迷宫中，以免妻子阿基坦的埃莉诺（Eleanor of Aquitaine）发现。亨利二世利用一个秘密的“窍门”找到正确的路线，到达幽会地点。根据传说，埃莉诺也找到了一个“窍门”：她沿着一根丝线追踪，也到达了迷宫的中心，令罗莎蒙德饮鸩自尽。这个故事是编造的，在14世纪以前尚未出现。罗莎蒙德的闺房是否真的存在，以现代的眼光看它是否称得上迷宫，这些问题都很难说。不那么浪漫的历史学家猜测，它不过是一座设计简陋的房子，外面有一些迷惑人的通道。
现代迷宫差不多都是花园迷宫，通道两侧用角树（在英国常见）或紫杉制成篱笆封死。都铎王朝时期和斯图亚特王朝时期，花园迷宫在英国很兴盛。迷宫的设计者通常留出一条有记号的秘密路线通向出口，这是走迷宫的窍门。知道这个窍门，就可以毫无困难地找到出路，出入自如。
迷宫留下许多奥妙。走迷宫问题属于NP完全问题。它是一类普遍性的问题中的一个，有可能难倒最强大的计算机。
NP完全
世界就是一个由纵横交错的关联和关系组成的迷宫。“NP完全”（NP-Complete）这个名称客观而准确地表达了这种状态。从字面上看，“NP完全”是“非确定性多项式时间完全”（nondeterministic polynomial-time-complete）的缩写。这个令人望而生畏的术语定义了一个基本而普遍的问题种类，在哲学思辨和实际应用两方面都有重大意义。
NP完全问题是30年来始终困扰着计算机程序员的一类问题。计算机自问世以来，其运算速度越来越快，功能越来越强大。20世纪80年代末的计算机的运算速度大约比50年代末的计算机快3万倍。有一个炫耀的说法：“如果汽车技术的发展与计算机技术保持相同的速度，那么相当于一辆劳斯莱斯汽车应当以超音速行驶，而价格低于1美元。”然而，在20世纪60年代中期，计算机科学家开始意识到有些事不对劲。有些普通问题极难用计算机解决（也很难用已知的方法处理）。采用更强大的处理器或者投入存储空间更大的内存也无法产生可以期望的差别。这些问题逐渐被称为“难以处理的”或“内在困难的”。
“旅行推销员”问题即为一例。许多古老的谜题书都介绍过这个问题。这是一道数学题：一个推销员必须到达几个城市，城市之间的距离已知，要求你为一个推销员设计一条最短路线。这个问题击败了最强大的计算机。关键在于组合数学，一个本身不太大的集合产生了数量巨大的组合。解决这个问题的已知的最好办法并不比比较每一条可能路线的总英里数高明多少。随着城市数的增加，计算量如雨后春笋般激增，很快就突破了任何可以设想的计算机的计算能力。
NP完全作为一类问题首次在1972年的一篇论文中得到清晰的表述，论文的作者是加州大学伯克利分校的理查德·卡普。从此以后，NP完全在几十个意外的领域受到关注。小孩的谜语、谜题、游戏和脑筋急转弯中有许多NP完全问题的例子。如果找到了可高效解决NP完全问题的“解法”，那将是价值连城的发现（不过大多数计算机科学家认为不大可能找得到）。美国、苏联以及其他技术发达国家的军事安全在这个时代以NP完全为基础[1]，而这个基础并不牢靠，在信息时代，再没有什么比这更令人如芒在背了。超级大国的敏感数据是用“公开密钥”密码保护的，这种密码以大型的、实际不可解的NP完全问题为基础。类似的密码为商业私人数据和政府数据库提供安全保障。许多种类各异的问题实际上是相互等同的，这个发现在哲学上也是发人深省的。毫无疑问，“很少有技术术语像‘NP完全’这样快速地声名远播”——麦克尔·R·加里（Michael R.Garey）和大卫·S·约翰逊（David S. Johnson）影响广泛的著作《计算机与难以驾驭性：NP完全理论导论》（1979）就以这句话开篇。
“NP完全”是一个非常难以理解的抽象说法。我们最好用具体的例子解释一下。迷宫不仅可以用来比喻我们对知识的探求，在方法论上，迷宫还等价于我们的逻辑方法（从一个适当的、抽象的视角看）。迷宫预示了演绎方法中的核心问题——悖论发现问题。
迷宫算法
我们以这个问题开始对NP完全的探讨：是否存在解迷宫的一般方法？
是的。事实上，存在好几种方法。并非所有的迷宫都需要动脑筋。单行线迷宫从头到尾都只有一条通道，没有岔道，没法走错。许多中世纪的迷宫迂回曲折但是没有岔道，唯一的通道会通向一棵树或一座神殿。早期的英国教堂墓地设计成这种类型的迷宫，象征迂回曲折的人生道路——虔信者在世间邪恶的诱惑下穿行。
克诺索斯的弥诺陶迷宫可能就是没有歧路的。钱币的图案显示了一条没有岔道的通道。如果你在这样一座迷宫里遭遇弥诺陶，你只需做一件事：掉过头跑。这样你永远都不会走进死胡同，另外，也许这些钱币只是表明一种设计风格，而非一张真正的地图。还有一种可能：这些图案也许展示了在更复杂的通道网络中应当怎么走。除非有岔道，否则你用不着拿一根丝线标记路线。
每座迷宫至少有一个入口，而且大多数迷宫都有一个终点——在迷宫中你试图到达的一个地点。终点通常在迷宫的中心附近，当然，终点也有可能只是迷宫边界上的一个出口。[2]破解迷宫的目的是找到一条路线，从入口走到终点。路线也许只有一条，也许有多条。当连接入口和终点的路线不止一条时，一个潜在的谜题是发现最短路线。
有些迷宫的入口不止一条。这与仅有唯一入口的迷宫并无本质不同。你的第一个选择是从哪个入口进入，这个选择是在进入迷宫以前做出的，但是这与在迷宫内选择路径没什么两样。有些迷宫有多个终点，要求游客走遍迷宫的各个部分，或者一系列由雕像、长椅或其他东西标示出来的地点中的每一个。路易十四在凡尔赛建造了一个著名迷宫，游客需要找到39座根据伊索寓言设计的雕塑。每座雕塑的原型都是伊索寓言中会说话的动物，水柱从它们的嘴里喷出来，形成喷泉。最后，还有一类迷宫是没有终点的，这种迷宫的走法就是进去闲逛，然后找条路出来。
在迷宫格局中，每个分岔处称为一个“节点”。节点是通道交叉的地方，在节点处你必须做出选择。入口、终点和死胡同的终端也被视为节点。两个节点之间的通道被称为一个“枝”。任何迷宫都可以用简化的图来表示，在图中，“节点”用点表示，“枝”用线表示，点和点之间用线连接。用数学术语来说，迷宫是一张“图”。
几乎所有物理形式的迷宫都是二维的。这意味着，枝和枝之间从不交叉。在三维迷宫中可以有天桥和地道，枝和枝可以交叠，如同高速公路的立交桥。
在图上解迷宫和实际走迷宫不是一回事。面对谜题书上印出来的迷宫地图，通常只利用眼睛就可以解决，人眼会自动地把迷宫当作一个“完形”。但是当你身处于一个实际的迷宫内部时，通道两侧被篱笆或石头封闭，你很难在头脑中形成一个整体图像。高明的设计者会把某些节点设计得非常相似，让你觉得自己在同一条路上兜圈子，而实际上你到达的是一个新地点。此外，在图上解迷宫可以用一些由来已久的方法，例如，把终点当作起点进行倒推（这种方法有时使问题简化，有时则更麻烦），或者勾掉所有死胡同，从而使路线变得更清晰。但是在实际的迷宫内部，这些法子都用不上。
迷宫的难度与各节点处发出的“枝”的数量息息相关。如果每个节点处都只有一个枝，那么这个迷宫一定是单行线迷宫。我们可以把节点想象成两颗珠子，在珠子之间有一条线，无论这条线如何盘旋环绕，一个不变的事实是，它总是连在两颗珠子之间。沙特尔教堂的迷宫就是单行线迷宫，这个迷宫没有墙，是用蓝色和白色的大理石在地板上铺出来的。
如果每个节点处有两个枝，迷宫同样毫无难度可言。我们可以把它设想成一堆珠子串在一条线上。走这样一个迷宫时，你不用做出选择。实际上，你通常不会把连接两个枝的连接点视为一个节点。把这两个枝看作连续的一个枝更简单，所谓的节点不过是在这个枝上打了一个结。
在迷宫里，一个真正的岔道至少需要几条通道汇聚在一个点（三条路形成三岔路口）。节点处汇聚的枝越多，迷宫就越难走。
大多数近年来的迷宫按照习惯采用了接近直线的设计，道路和限制通道的篱笆构成密密麻麻的蜂巢，填满整个区域。这使得此类迷宫比每个节点发出四个枝还要难。凡尔赛迷宫采用了更灵活的设计。各个枝不必要地平行，许多枝汇聚在一个单独的节点上。最高纪录是一个节点上汇聚了5个枝。凡尔赛迷宫的设计师安德烈·勒诺特雷（Andre Le Notre）在尚蒂伊建造了另一个迷宫，其中心节点汇聚了8个枝。
下表介绍了关于几个著名迷宫的统计数据。有几处，节点和枝的数目应当如何计算有待商榷。在每个场合，细心的游客需要做出决定的地点都被我算作一个节点，入口、终点和死胡同的终端也被当作节点，但是只有两个枝的冗余节点被排除在外。最后一列是平均每个节点汇聚的枝的个数，这个数量大致反映了迷宫的难度。
凡尔赛迷宫
右手法则
最著名的迷宫算法是“右手法则”：每当你面临选择时，选最右面的枝。如果走到了一个死胡同，折回来退到上一个节点，选择你没走过的枝中最右面的一条。为了具体地应用这条法则，最好的办法是始终用右手摸着右侧的篱笆，绝不漏掉右侧的枝。
当然，右手本身没什么特别之处。采用“左手法则”一样行得通。唯一需要注意的是，一旦进入迷宫，就必须坚持同一条法则。
为什么这条法则行得通？它不是一个单纯的习俗。“按顺时针方向拧紧螺丝”是一个单纯的习俗，但是你完全可以制造一枚螺纹方向相反的螺丝。右手法则比简单的习俗更深刻，它依赖于迷宫的拓扑结构。
我们来研究一张画在纸上的迷宫的规划图。被篱笆封锁的区域涂成绿色，绿色区域之间的白色部分是迷宫中可以通行的部分。在许多迷宫中，被篱笆封锁的区域连成一片。此时实际上只有一道篱笆，尽管它可能是蜿蜒曲折的。这个迷宫看起来像一个形状诡异的国家。对比地图上的国家，代表国土的绿色区域被边界线包围。边界线是一条单独的封闭曲线（边界线对应迷宫的篱笆）。这条曲线的任何一个部分与任何一个其他部分是连在一起的。因而，走迷宫的时候，只要把右手放在篱笆上耐心地往前走，一定会经过迷宫的所有部分。
前文提到童子军迷路算法——沿着溪流可以找到有人烟的地方，实际上，右手法则的基本原理与此类似。整个北美是一块大陆，北美的海岸线（包括江河构成的凹陷）是一条封闭曲线。沿着河岸或者海岸线走，最终一定会到达新奥尔良（也可以到达任何一个位于河流或海岸线上的地点）。在迷宫中，也许会包含被篱笆分隔开的“岛屿”，但是，只要入口处的篱笆和终点处的篱笆属于同一个岛屿，右手法则就可以生效。
右手法则（或者左手法则）的优点是简单。它的缺点有两个：首先，效率不高。跟随这条法则你会走遍右侧（或左侧）的每一条死胡同。在大多数场合，存在一条通向终点的短得多的路线。其次，右手法则并非在所有迷宫中都能生效，这一点更为糟糕。显然，所有已知的、在19世纪20年代以前建造的迷宫用这条法则都能走通。此后，数学家斯坦诺普伯爵设计了一个更复杂的迷宫，它坐落在肯特郡的切佛宁。
切佛宁迷宫有八个被篱笆分隔开的“岛屿”，因而右手法则不再有效。入口和终点不在同一个岛屿上。如果你依照右手法则走这座迷宫，你会围着一个区域兜圈子，永远无法到达终点。（就好比在长岛沿着河岸和海岸线走，永远无法到达新奥尔良一样。）这类迷宫需要一个更复杂的算法。
特雷莫算法
所有更强大的迷宫解法都需要某种方法以确保人们不是在兜圈子。你需要在路上做标记，沿路放丝线、撒面包屑、折弯树枝，如此等等。否则，你必须有极好的记忆力，能记住篱笆的形状，并且保证自己能认出所有曾经走过的地点。
有一种名为“特雷莫算法”的通用方法可以确保解决任何迷宫问题。根据法国数学家爱德华·卢卡斯（Edouard Lucas）的《娱乐数学》（1882）一书的记载，这种方法是特雷莫（M.trémaux）发明的，因而命名为特雷莫算法。这种方法可以说是前文提到的特修斯沿路放丝线的方法的精细化算法。
切佛宁迷宫（篱笆围成的外部“岛屿”以黑色表示）
特修斯沿路放丝线保证自己可以原路返回入口处，不至于迷路。但是丝线不能帮助特修斯找到弥诺陶的窝。特修斯可能会走到某个岔路口，发现自己在兜圈子。当他决定下一步选哪一条路时，他可以利用这个信息加以改进，这种想法是合理的。特雷莫算法就是这么做的。
走进迷宫后，首先随便选一条路，沿路做记号，可以利用丝线或任何手边的东西（下文的叙述中采用面包屑）一直走，直到达到目标（如果走运的话），或者走进一条死胡同，或者迷宫中的一个你以前来过的岔路口（证据是你留下的记号）。
一旦走进一条死胡同，就退到上一个节点。（你别无选择！）记住在回来的路上也要做记号。如果你曾经在一条死胡同里一进一出，路上将留下两行面包屑。这个记号提醒你下次不要再走进去。在特雷莫算法中，任何一条路你都不会走两次以上。
当你走到迷宫中的一个以前来过的节点时（可能是通过另外一条路来过），进行如下操作：
如果你是从一条新路到达的（也就是说，你的身后只有一行面包屑），转身沿原路退回上一个节点。否则：
如果有一条没走过的路，选择这一条。否则：
任选一条以前只走过一次的路。
这就是全部需要遵守的规则。根据特雷莫算法，你会在迷宫内完成一次完整的旅行，每一条路你都走过了两次，两个方向各一次。当然，在到达终点以后就可以停下了，没有必要完成整个巡回。
和右手法则一样，这种算法的效率极低。当然，你有可能非常走运地从入口直接走到终点，但是可能性更大的是，你走完了迷宫的大部分甚至是全部以后才到达终点。
在什么时机采用右手法则或者特雷莫算法都不算晚。你可以走进一个迷宫，随心所欲地走，在迷路以后再采用算法。在任意一个点都可以开始执行算法，把这个点当作另一个“入口”。特雷莫算法将引导你从这个点出发完整地游历整个迷宫，包括终点和实际的入口。这两种算法不仅可以用于花园迷宫，在令人晕头转向的建筑中也有效。如果你在五角大楼或卢浮宫里迷路了，你可以利用特雷莫算法走出来。
无限的迷宫
设想一个面积无限延展的迷宫。这个迷宫无边无际，遍布整个世界，所以根本没有入口和边界。你从迷宫中的任意一个点开始探索，你不知道自己在这个宏大的迷宫中的位置，正如我们不知道自己所处的星系在宇宙中的位置一样。
这个迷宫的结构非常简单。在每个节点上，恰好有三个枝交汇。各个节点通过标记相互区分，雕像、长椅、树木等各种各样的东西都可以充当标记，你寻找的终点可能就是其中的某一个。
和所有其他迷宫一样，这个迷宫在本质上也是非理性的。在寻找一个给定的目标的过程中，没有哪一条路比其他的路更优先，任何一条路都可能是“正确的”。正确与否依赖于这个迷宫是如何建造的。这个迷宫的结构是通过无止无休的自我复制实现的，在复制过程中又加入了变化——意识到这一点令人绝望。假定一个游客花了若干年探索迷宫中的一个特定区域，到达了已知区域的边界上的一个岔路口。他面对两条未探索过的枝，其中一条通向他寻找的标记，但哪一条是呢？实际上，在整个迷宫中他已经探索过的部分一定会多次重复，在某些重复结构中，熟悉的路线连接迷宫的其他部分，因而，右侧的路通向终点；但是在其他场合，左侧的路才是正确的。当然，这个游客无法知道他当前的处境属于哪种情况。对于任何企图以理性的方法选择路线的计划，这都构成了一个嘲讽。
假定你处在这个无限的迷宫中，闲逛了一段时间之后，绝望地发现自己迷路了。你没有沿路做标记，也不知道自己究竟走了多远。
在这个困境中，你不想采用特雷莫算法。只要你新走的路没有和以前走过的路交叉，特雷莫算法就不会对你的行动给予任何指导。你有可能在迷宫中深入若干英里，越陷越深。在一个无限的迷宫中，你甚至有可能从未与自己走过的路交叉，从未见到终点，也从未再次遇到熟悉的地点。
特雷莫算法和右手法则预先假定，即使走遍迷宫的全部或一个很大的部分也没什么大不了的，只要确保自己不是在不停地兜圈子，最终到达终点就行。特雷莫算法实际上鼓励优先探索迷宫中较远的区域。根据此算法，选择未走过的枝总是优先于熟悉的枝，而且，除非不得已，你应该尽量避免与自己走过的路交叉。在有限的迷宫中，这些建议是合理的，因为终点几乎总是距离入口相对较远。否则的话，迷宫的主人就浪费了自己的地产，付给维护灌木的园丁工资，却没有增加迷宫的趣味性，这是没道理的。
但是在无限的迷宫中，你不能浪费时间在未知的区域漫无目标地闲逛。当你迷失方向、但确知目标比较近（与迷宫的整体大小相比）时，你应当首先探索邻近的区域，在必要时再向外扩展。耶鲁大学的厄于斯泰因·奥尔（Oystein Ore）在1959年介绍的一种算法就是如此。
奥尔算法
为了解释清楚这种算法，最好假定你从一个节点开始。如果你的出发点不是一个节点，那就走到最近的一个节点处。如果不知道哪个方向可通向最近的节点，随便选一个方向，走到你遇到的第一个结点。这个点就是你的出发点。
从出发点开始，探索交汇于此的每一个枝。在进入每一个枝的时候，在入口处放一块鹅卵石。对每一个枝的探索仅限于到达下一个节点，然后在这个枝的终点处放一块鹅卵石，原路返回出发点。
如果遇到死胡同，你就做一个标记。一旦对一个枝做了死胡同的标记，以后就可以忽略这个枝了。做标记的方法可以是在死胡同的入口处拉一条封锁线，或者摆上一排鹅卵石。
如果某条路转了一圈又回到最初的节点，那么你也要把它标记为死胡同。这种路对你也是无用的。
你的兴趣在于确定那些通向有新枝的新节点的枝。在探索的第一个阶段结束之后，每一条有可能通向终点的潜在路线都已经做了记号——路的两端各有一块鹅卵石，而你重新回到了出发点。
下一步，探索的深度达到两个节点。沿着每一条非死胡同的枝走到新节点，从这个新节点出发探索每一条由此辐射出去的枝，探索方法照旧。在最初的那个枝的两端各加一块鹅卵石（此时，这个枝的两端各有两块鹅卵石），对于新探索的第二级的枝，两端各放一块鹅卵石。这个办法可以防止你找不到返回出发点的路，可返回出发点的路有一个特点：路口处的鹅卵石比其他路口多一块。和第一阶段一样，对死胡同和兜圈子的路做标记，予以排除。如果一个枝通向以前探索过的节点（这个节点至少有一块作为记号的鹅卵石），在这个枝的两端也做标记，予以排除。
探索的第三步，深度达到距出发点三个节点处，在每一个探索过的枝的两端各加一块鹅卵石。依照以上规则不断推进探索步骤，直到发现终点、入口或者其他想找的东西。
奥尔算法可以确定通向终点的最短路线（所谓最短是指枝的数量最少，而非物理距离最短）。当然，你的探索过程不是最简的。但是，如果最短路线需要经过五个节点，你一定可以在探索的第五个阶段发现它，而且可以确保它是最短的。
奥尔算法的效率同样低得可怜。它不是直接对准正确的路线，而是检查所有可能的路线。这是必不可少的，因为任何一条路线都可能是正确的。
迷宫的NP完全性
下面考虑一个问题。这个问题也许可以称为无限迷宫问题。你位于E点（E点代表入口，不过这个点和其他点一样，淹没于无边无际的无限迷宫中），你在寻找G点，这个点代表终点，终点可以是迷宫中的任意点。你不知道G点在哪儿，无法在地图上对G点定位（根本就没有地图）。你确信，如果你走到了终点，便可以认出它来，因为终点处有一个已知的标记。根据以上对迷宫的明确规定提出我们的问题：“连接E点和G点的简单路线是哪条？”
所谓的“简单路线”，是指不出现自身交叉的路线。如果路线自身交叉，就是在兜圈子。兜圈子总是不必要的，而简单路线要求的成本较低。简单路线可能不止一条。如果存在多条简单路线，其中最短的一条更受欢迎。但是，对于一条简单路线是否具备“最短”这个优点，你并不是很在乎。毕竟，探索这个无限迷宫是一个令人恐惧的任务，几乎任何一条能通向G点的路线都是令人满意的。
另一个问题与无限迷宫问题密切相关，这个问题可以称为“迷宫存在性问题”：是否存在从E点通向G点的简单路线？
我们来看一下为什么这个问题比较简单。一旦无限迷宫问题得到了答案（具体指明了一条路线），这个答案本身就回答了存在性问题：简单路线确实是存在的。即使它无法具体地指明一条路线，在某些情况下，仍有可能表明简单路线是存在的。我们很自然地认为，一个只需回答“是—否”的问题要比一个也许需要为一个长达数十亿个枝的路线不厌其烦地定向的问题简单。
只有怀疑主义者才会问存在性问题。大多数迷宫探索者有一个基本观念：所有的点都是以某种方式连在一起的，从此处总可以走到彼处。尽管路线可能曲折而漫长，但是它毕竟是存在的。然而，实情未必如此。有这样一种可能：迷宫是骗人的，它只有问题却没有答案。也许所有道路构成了两个互相缠绕但彼此分离的网络，从一个部分无法到达另一个部分。即使假定整个迷宫属于一个单一网络，对此我们也永远无法证明，因为我们的知识仅限于迷宫的局部。在一条具体的路线被发现并得到证实以前，我们总是可以设想通向目的地的路并不存在。
这个“存在性问题”属于NP完全问题的一种，被称为“最长路径”问题。NP完全问题以“困难”著称，但是这个存在性问题有时不难回答。例如，当G点碰巧距离E点只有一个枝时，随机的探索几乎会立刻发现G点，存在性问题和无限迷宫问题同时得到解决。
这很正常。一个一般性问题的特例有可能非常简单。我们要寻找的是解决存在性问题的成体系的通用方法，这对于最简单的迷宫和无限的迷宫都有效。
对于一个未知的迷宫而言，不存在快速的解法，事先我们无法知道哪条路更好。我们所能采取的最好的方案就是检验几乎每一条路，直到发现终点。各种各样的迷宫算法其实只有一个功能：避免不知不觉地兜圈子或者在已知的死胡同和环道上浪费更多的时间。在探索迷宫中的新领域时，算法并不能给你“聪明”的指导。
我们看一下奥尔算法，这个算法的效率和其他算法一样。你从出发点开始可以发现：这个节点发出了三个枝，每个邻近的节点同另外两个节点相连。（在一个邻近的节点上有三个枝，其中一个枝把这个节点与出发点连在一起，这个枝已经考虑过了。）这六个点中的每一个依次与另外两个节点相连，这样新的节点距离出发点又远了一层。迷宫的节点和枝层出不穷。你探索的枝把你带到新的节点，而新的节点又产生更多的枝。这些枝中的一部分可能以前探索过（根据以前做的记号可以证明）。在多数场合，需要探索的枝的数量呈指数关系剧烈增长。你对迷宫的了解越多，你就越感觉到自己对迷宫的无知。
假定探索一个枝需要1分钟，奥尔算法的执行过程大致如下：
在所有有限的迷宫中，发现新枝的过程最终一定会结束。在某个具体的探索阶段过后，大多数新枝会指向已经去过的节点。最终，所有的枝都被走过了，终点一定已经发现。然而，在无限迷宫中，指数增长永不停息。即使终点相对较近，找到终点也会耗费大量的时间，以至于实际上难以找到。也许相距5个节点，需要花费将近一天的时间，但是实际上一旦发现了路线，走到终点只需要5分钟。搜索一个15个节点远的终点需要若干年。如果到终点的距离是45个节点，那么为了找到终点，宇宙的全部时间都不够用。
我们从计算机程序员的角度来看一下最长路径问题。你希望用计算机来判定，在一个比较大的迷宫中的两个点是否被某条路线连在一起。为此，你必须为计算机提供一幅迷宫“地图”。这幅地图以表格的形式列出了迷宫中的所有节点和所有的枝。节点标明数字或名字，通过明确一个枝连接哪些节点以及节点之间的距离可以确定枝。（无论采用什么计数单位，距离都用整数表示。）一个枝可能被表示为“节点16，节点49∶72英尺”。距离是游客所走的实际长度，而非直线距离。充当入口和终点的节点同样如此表示。
最长路径问题还需要考虑一个因素：一个特定的距离n。最长路径问题问的是，在入口和终点之间是否存在长度大于n的直接路径。如果你愿意，n可以取任意小的值，甚至是0。当n取0时，最长路径问题转化为：是否存在一条长度大于0的路径，这等价于是否存在一条连接入口和终点的任意形态的路径。
既然存在性问题属于NP完全问题，比它更难的无限迷宫问题至少和NP完全问题一样难。如果判定通向G点的路径是否存在这个问题的难度已经达到了实际不可解的程度，那么具体指明这样一条路径的问题更是如此。
迷宫先知
NP完全问题有一个令人惊异的属性：其答案很容易验证。设想你遇到一个先知，无论你问什么问题，这个先知都能依靠神的启示立刻给出答案。那些相信先知的全知能力的人带着问题来问先知，这些问题如此之难，以至于他们解决不了，但是先知却能立即做出回答。
然而，当先知试图向所有人证明自己的特异功能时，他遇到了麻烦。他的想法是，通过表明他给出的答案的正确性来证明自己确实是全知的。但有时这是不可能的。
人们问他的问题分两类。最常见的一类是其他人无法回答的难题：为什么存在邪恶？神存在吗？圆周率的十进制小数展开式中小数点后第10100位数字是几？实际情况是，先知的回答从各个角度来说都是正确而精准的，但是他无法证明这些答案。怀疑者对他冷嘲热讽：对于这些问题先知可以胡乱给出任意的答案，反正别人也无法揭穿他。即使是相对而言比较现实的问题（例如圆周率的第10100位的数字）也难以验证，其难度已超出了世界上最强大的计算机的处理能力。
为了证明他的特异功能，这个先知必须回答那些答案可以被检验的问题。人们问他的问题中也包括这种，其中某些是怀疑者提出的，提问的目的就是拆穿他。基里巴斯的首都是哪儿？622 521的平方根是多少？《小妇人》中的姐妹们叫什么名字？这只密封的箱子里装的是什么？
先知正确地回答了所有这些问题，而且提问者知道先知的答案是正确的。提问者知道这一点，是因为提问者本来就知道答案。问题就出在这儿。这些问题太简单了，因而不足以确切无疑地证明先知的神力。既然提问者早已通过普通的方法知道了答案，那么可以设想，先知同样可以利用普通的方法了解或发现。怀疑者会说，他的全知可能是假冒的：他不过是一个计算天才，在一些琐细的事情方面的知识非常渊博。至于最后一个问题，他采用了“测心术”——表演者在舞台上施展的不入流的骗术。
这两种结果都是先知的失败。如果一个问题是其他人无法回答的，怀疑者会指控他捏造；如果一个问题的答案是已知或者可知的，怀疑者会指控他假冒。为了证明自己的全知，先知需要第三类问题，其特点在于：问题很难回答，可一旦说出答案，便很容易验证。存在这样的问题吗？
无限迷宫问题就满足这个要求。让怀疑者在这个迷宫中选两个随机点，然后让先知在两点间确定一条路线。任何人都能轻而易举地验证答案正确与否，他们需要做的不过是沿着指定的路线走，验证一下自己是否到达正确的地点。
这个问题不会是另一个“简单”的问题吗？我们必须确保选定的这两个点足够远，没有人知道连接这两个点的路线，甚至没有人可以用正常方法找到一条这样的路线。算法（包括奥尔算法）的相对低效性保证了这样一对点的普遍存在。如果两个点相距20个节点，用普通方法找到一条路线需要若干个世纪。[3]另外，这个问题不会是另一个“困难”的问题吗？不会，因为我们只需20分钟就可以检验先知的答案（假定每分钟走过一个枝）。迷宫的一个解比迷宫本身容易太多了。
就本质而言，第三类问题与复杂性理论中的“NP类”很接近。
P和NP
一个一般性的问题不同于一个问题的若干例子。拼版游戏是一类一般性的问题；把1 500块碎片拼起来，复原成一幅荷兰风车的图案。这是拼版游戏的一个例子。
NP完全理论判断问题的难度不是以某些特定的例子为依据，而是以难度随问题的规模增长而增长的函数关系为依据。在拼版游戏中，问题的规模反映为碎片的数量。碎片越多，问题越难。问题的难度最好用解题所需的时间衡量。当然，所需时间依赖于你的工作效率，但是这段时间显然与你为了完成工作而必须比照、处理的碎片数目有非常大的关系。
拼版游戏有一些非常困难的例子，例如有一种比较新颖的玩法，所有的碎片都是一种颜色。在这种情况下，你必须随机地比较碎片，判断它们是否吻合。在这个过程的早期，你需要把每一个碎片和许许多多的碎片比较，这个阶段会令你精疲力竭。比较和匹配操作的总体步骤与碎片数量的平方成正比。因此，所需的时间可以表示为包含n2的多项式函数，其中n为碎片的数量。
比较而言，这个问题所需的时间还不算多。在迷宫中，用奥尔算法找到终点所需的时间更接近于2n，其中n是起点和终点之间的节点数。当n较小时，n2和2n之间差别不算巨大；随着n值的增加，多项式函数和指数函数之间出现一条巨大的鸿沟。你可以解决一个有5 000个碎片的拼版问题，但是你无法解决一个需要5 000次正确选择的迷宫问题，除非迷宫明显非常简单。
从复杂性理论的角度看，所谓“容易”的问题是那些可以在多项式时间内解决的一般性问题。这些问题属于P类（P代表多项式）。我们把P设想为某处的一个辽阔的国家，粗略地画在地图上，但是边界是清楚的。地图上的任何一点或者属于P，或者不属于P。当然，我们的地图不大可靠，有时候无法判断属于与否。拼版问题是一个属于P类的点，简单的算术问题也属于此类。
另一类问题称为“NP”，包括所有那些答案可以比较容易地被检验的问题（可以在多项式时间内验证）。如果一个问题是简单的，那么答案也是容易检验的。如果别无检验的办法，你可以把问题重解一遍，比较一下两次的答案是否一样，这样就完成了检验。因此，所有简单问题（P类）属于答案容易检验的问题（NP）。NP还包括许多P以外的问题，迷宫就是一个例子。这样看来，NP像是一个更大的国家，而P是NP内部的一个省。如果画成地图，大致如下图。外面的矩形代表所有可能的问题。NP类并不包含所有的问题。有些极端困难的问题，甚至检验其答案都是很难的。矩形中NP的圆圈以外的部分代表这类问题。
我们在这个背景下讨论先知的问题。第一类问题是困难的，检验也是不容易的，它们相当于NP的圆圈以外的问题。第二类问题对应于P类。第三类问题难以回答但容易检验，对应于在NP范围内但不属于P的问题。
“NP”这个术语（“非确定性多项式时间”）涉及一种被称为“非确定性计算机”的东西。这种理想化的计算机会特别地被称为“图灵机”，这是计算机先驱艾伦·图灵（Alan turing）构想出来的。非确定性计算机与字面意思不大一样。从字面上看，它的意思似乎是计算机随机工作，或是遵循某种不大确切的“算法”（或者一台有自由意志的计算机）。
我们可以这样设想一台非确定性计算机的操作：我们的计算机不止一台，我们有很多台计算机，计算机的数量有可能是无穷多的。每一台计算机被分配了某个问题的一个可能解，以负责检验这个解。
例如，我们的问题是，要在迷宫中找一条路线，全体计算机（在这个例子中是机器人）从入口处出发。每当这支机器人搜索队走到迷宫的一个岔路口时，他们兵分数路，每条路分配一队人马。搜索队在每个新的岔路口不停地分派人马，直到把所有可能路线探索完毕。
至少有一个机器人实际上从入口走到了终点。现在我们集中考虑这个机器人。它用了多长时间？很可能没用多少时间。迷宫的解通常较短，迷宫的难度在于尝试所有错误的路径以及退回到出发点的过程。一台非确定性计算机用来“解”一个问题所需的时间就是用来检验一个猜出来的解的时间。
NP问题大致相当于科学探索所面对的问题。当科学家试图建立新的真理时，他的地位很像上文提到的先知。科学最关心的假说与NP问题的答案类似：这些假说可以非常容易地被证实或反驳。
在NP问题和科学之间还有更惊人的联系——逻辑演绎本身就是一个NP问题。
最难的问题
在NP类问题中，哪个问题最难？1971年，斯蒂芬·库克证明，“可满足性”和NP中的任何一个问题相比至少同样难。他的证明显示，在NP中不存在更难的问题，因为所有NP问题都可以转化为可满足性问题。
随之而来的是理查德·卡普的发现（1972）：许多不同种类的难题都属于可满足性问题。这些形态各异的问题来自图论、逻辑学、数学游戏、数论、密码学、计算机编程等领域，它们都和可满足性问题同样难。由最难的NP问题构成的类称为“NP完全”。用维恩图（Venn Diagram）表示，NP完全在NP的圆圈内，但位于P外。
严格地说，NP完全是一个不稳定的区域，也许并不真正存在。我们尚未证明NP完全问题无法在多项式时间内解决。我们的证据仅仅是经验性的：理论家和计算机程序员倾注多年的心血，试图在多项式时间内解决NP问题，但是毫无例外地失败了。在实际中，一旦证明一个问题属于NP完全，则可以认为有充分理由证明，这个问题不存在高效率的解决方法。
我们还可以勉强设想，存在一种尚未发现的超级算法，可以在多项式时间内解决所有的NP问题。如果确实有这种算法，那么P、NP和NP完全就全变成一回事儿了，我们可以把它们合在一起表示为一个圆圈。
如果存在一种高效率的解法——一个神奇的窍门，那么我们从逻辑前提中可以推出的东西 （像福尔摩斯那样）实际上就没有任何限制。反过来说，如果可满足性问题和NP完全问题没有高效率的解法，在现实中就一定存在大量的永远不会被发现的真理。我们强烈地感到，这样一种解法是不存在的。所有人都像华生医生那样，错过了大量可见的线索。
这意味着，对于哪些逻辑问题是可解决的，存在着一个关于其规模的相对严格的限制。在迷宫问题中，一旦迷宫规模超过一定限度，就变成实际不可解的了；同样的道理，一旦一个逻辑问题超过一定的复杂程度，也会变成实际不可解的。一个明显的推论是，我们关于实在世界的推理也是有限度的。
经验目录
悖论意义重大、影响深远，超过了其表面看起来的程度。如果某人相信一些自相矛盾的观念，那么这些观点中至少有一些是他没有理由相信的。因而，理解一组观点（至少）意味着有能力发现观念中的矛盾。所以说，发现悖论的问题——即可满足性问题——是知识的界标。在试图全面理解某事的含义的过程中，已经内在地包含可满足性的难度。
在奠定牛顿的万有引力理论基础的因素中没有一样是古希腊人不知道的。疾病的细菌理论原本有可能提前几个世纪提出和确立——如果某人发现了正确的联系。同理，此刻一定也有我们尚未完成的综合，虽然所需的材料已经摆在面前。非常可能的是，解决“如何预防癌症”、“第10颗行星在哪儿”这些问题所需的全部事实已然齐备，但是还没有人发现组织这些事实的正确秩序。不仅如此，也许我们正在错过关于这个世界的各种各样的逻辑结论。这些结论有可能隐藏在我们见到、听到的每件事里，但是其复杂性有一点点超出了我们的理解力。
爱因斯坦写道：“全部科学的宏大目标是，从最小数量的假说或公理出发推导出最大数量的经验事实。”[4]把人类的全部经验加在一起，包括从冰川纪至今所有人曾经看到、摸到、听到、尝到或闻到的一切。从理论上说，这些信息可以汇集为一个巨大的目录，这个目录是一个简单的列表，对经验不做任何解释。对梦境、幻象、胡思乱想和错觉详尽描述，与“真实”的经验并列。二者中哪个是真实经验（如果有的话），留给目录的读者自己确定。
这个目录必然包含作为自然科学的基础的全部观察。对鸟、星星、蕨类植物、水晶和草履虫的全部观察都可以在目录中找到。这个目录也包含所有曾做过的科学实验中的那些哪怕最微小的细节。目录中还包括，在1887年那个特殊的日子，迈克尔逊和莫雷对下午稍晚时候的阳光照耀在仪器的镜子上的印象。[5]牛顿曾见过的所有苹果的颜色、尺寸、形状、运动速度以及加速度等信息也被搜集在目录中。
科学不是简单的经验目录。首先，任何人的大脑都无法容纳全部人类经验的整体。目录必须包括你经历过的一切，这就会占据迄今为止你的整个生命中的全部注意力！科学对人类经验（或经验的某些方面）进行压缩，达到一个可处理的形式。我们真正感兴趣的是理解目录所描述的这个世界。总的说来是这样，虽然某些特殊场合并非如此。在科学哲学中有一个恼人的问题：这种过程可能进行到何种程度？
每一个经验对未知的世界的某些部分的真值都做出了限制——和在逻辑谜题中一样。当然，未知事物间的关系可能非常微妙，每一个事物都必须用一系列的“如果”来限定。也许你的一个经验是：你听到你的朋友弗雷德说，他上个星期二见到了尼斯湖怪兽。经验的实际输入也许是这样：
如果弗雷德没犯错，他也没有撒谎，并且外部世界不是幻象，那么在星期二尼斯湖怪兽存在。
这些“如果”从句是必不可少的辅助性假设，它们使证实复杂化。
把经验目录输入一台超级计算机，编好程序，让它进行推演。这个任务只需要逻辑，而逻辑正是计算机的强项。在这个任务完成以后，计算机甚至可以把推演结果按重要性排序，重要的衡量标准是一个结果可以解释多少不同的经验。推演结果列表的第一条应当是人类可以知道的最重要的事实。
虽然以上介绍只是幻想，但是它确实展现了科学哲学中某些最核心的问题的基本框架。连锁推理是科学的基础，它的一致性可以在多项式时间内识别和检验。这些简单的逻辑问题相当于单行线迷宫（在每个节点处只有一或两条枝的迷宫），简单得不值一提，并且与“正常”的迷宫（每个节点处有三条或更多的枝）不同。更复杂的推演包括含有三或四个未知量的前提，解这类问题需要指数时间（实际上是无法完成的）。也许有一大类可以解释我们的感觉经验的逻辑推演是我们永远无法发现的。
把我们的经验设想为迷宫，把关于经验的逻辑真理设想为遍布迷宫的路径。可满足性问题的NP完全性表明，我们永远无法穷尽所有的潜在路线。
和宇宙一样大的计算机
计算机科学家拉里·J·斯托克迈耶（Larry J. Stockmeyer）和阿尔伯特·r·迈耶（Albert R. Meyer）设想了一台大小和宇宙一样的计算机，以此来形象地展示处理NP问题的极高难度。他们表明，我们在想回答许多关于宇宙的问题时，会发现宇宙并不够大。
假定我们试图把所有已接受的观念列成一个清单。就像笛卡儿一样，我们希望从一片空白开始，并且非常小心地把观念填进去。在任何一个观念被填进去之前，首先再次检查已经被列进清单的观念，以确保增加的新观念与已有的观念不产生矛盾。这个检验即为可满足性问题。
也许你会认为，为此只需要把清单浏览一遍，确保准备加入的新观念不与任何一个以前列入的观念直接矛盾。然而，实际情况没有这么简单。
显然，新的观念有可能与旧的观念矛盾。如果新的观念是“所有乌鸦都是黑色的”，而旧观念中有一条“所有乌鸦都不是黑色的”，在这里你就遇到了矛盾。[6]最危险的是这种情况：三个或更多命题，各自独立地看都是可以成立的，但是合在一起构成矛盾。通常，“悖论”这个术语专门指这种情况，矛盾不是一目了然的。
假定新的观念是“所有草都是绿色的”，清单中可能已经包含了两个语句：
所有干草都是黄色的。
干草是草。
这两个语句若加上新语句就产生了矛盾。如果你仅仅一对一对地检查——在三个语句中拿出两个来检查是否相互一致，你就会遗漏这个矛盾。为了排除这种情况，有必要在清单中一对一对地取出所有可能的命题组合，一一检验它们加入新命题后是否一致。这极大地增加了检查的工作量。但是这还不算完。也许还有更精致的悖论，只在四个、五个或更多命题合在一起考虑时才显现出来。在100万个观念中加入一个观念，即使在原来的观念中任意取出999 999个观念与新观念合在一起都是一致的，整体上还是有可能出现矛盾。
需要检查的事实太多了，显然必须借助于计算机。我们从l号观念开始（这个观念也许是“我思故我在”）。为了让计算机能够处理，这个观念被表示为关于布尔未知量的一个逻辑命题，下一步，我们准备加入一个新的观念，2号观念。我们指示计算机对照1号观念进行检查，看看是否出现矛盾。此时，只需一次逻辑检验（比照2号观念和1号观念）。
现在，清单中有两个观念，我们准备加入第三个。此时必须进行三次检验：与1号观念比照；与2号观念比照；与1号、2号合在一起比照。
第四个观念必须和7个命题集合进行比照：分别与1、2、3号比照；分别与1和2、1和3、2和3比照；与l、2、3合在一起比照。
事实上，一个新的观念必须与当前清单上的所有可能子集合在一起检验。n件东西的子集数计算公式是一个指数函数：2n。这个公式把空集也计算在内，其实我们不必考虑空集。非空子集的数量是2n–1。
假定这些观念（或其中的某些信息）在逻辑上足够复杂，因而无法避免指数时间的算法。此时，需要进行比较的次数如下表：
即使这个清单的规模非常有限，比方说，只包含100个观念，它的子集数也是一个天文数字。为了接受第101个观念，它必须与这个清单包含的1030个子集对比检验。
怎么会这样呢？你可以写下第101个观念，然后很快地确信其中并无悖论，这不是很明显的吗？
确实如此。你可以随机从一部百科全书中抄下100个命题，确保每个命题都提到一些别的命题没说的东西。但是，我们现在研究的是更一般的情况，清单中的观念可能有许多是关于同一个未知量的，而且逻辑关系是复杂的。这些观念有可能互相纠葛，就像卡洛尔猪排问题的前提那样。这样我们就必须求助于一种算法——一种很慢的算法。
计算机向清单中加入观念的过程可以快到什么程度？
斯托克迈耶和迈耶在分析时，假定有一台“理想”计算机依靠指数时间算法确定某些数学命题的真假。就本质而言，这个分析对可满足性问题同样有效。斯托克迈耶和迈耶认为，任何一台计算机的计算能力最终取决于它所包含的元件的数量。在计算机体积一定的条件下，元件越小，处理能力越强。
在最早的数字计算机中，逻辑门采用真空管，而连接采用导线。后来，真空管让位于晶体管。现在，强大的处理器封装在一个芯片内。大多数连接是通过印制电路实现的，它们由很薄的金属膜构成。
没有人确切地知道，处理器和逻辑门可以小到什么程度。在实验条件下，逻辑门可以采用只有几个原子厚度那么厚的膜。在这个领域，许多前途远大的技术尚待开发。斯托克迈耶和迈耶在他们的思想实验中采用了非常乐观的假定。他们设想，计算机元件以某种方式可能达到质子的大小。现在我们认为，在可测量的范围内，质子和中子是最小的。在这台理想计算机中，无论元件多么小，其直径不能小于10–15米（负的指数表示分数，这个数是1除以1015，即一毫米的一万亿分之一）。
假定这些质子大小的元件可以像沙丁鱼罐头那样密密麻麻地塞满在一个体积给定的物体内，它们可以填充多少个直径为10–15米的理想球体，就可以填充同样数量的元件。如果计算机的大小与普通的个人电脑相仿（体积大约为1/10立方米），则大约包含1044个不同的元件。一个体积为一立方米的小型机将包含1045个元件。
在计算机技术中，另一个头等重要的因素是速度。一个元件需要花费的时间（例如一个逻辑门从一个状态转换到另一个状态的时间）构成瓶颈，任何形式的信息最快只能以光速传播。因此，一个元件转换状态的时间不能超过光通过它所需的时间，否则就意味着，元件的一端以超过相对论所允许的速度“得知”另一端发生的情况。
光穿过一粒质子的直径所需的时间是3×10–24秒。在斯托克迈耶和迈耶的分析中，理想计算机的元件转换状态所需的时间采用这个值。
在现实中，计算机的速度还依赖于元件之间的连接方式以及为处理问题配置的可用资源的完善程度。大多数现在的计算机是串行的，也就是说，在某一个时刻计算机只处理一件事。在任意一个瞬间，计算机处于算法中的一个点。就潜力而言，并行计算机的速度快得多。并行计算机有很多处理器，总任务被分解为子任务，交给各个处理器。在大多数时间里，并行计算机能够同时做许多事。
我们不妨奢侈一些，假定这台理想计算机按超精密的并行结构设计。每一个质子大小的元件是一个单独的处理器。各个处理器用某种类似于连接机器的方式连接起来，以确保相对直接的连接——即使处理器的个数是天文数字。
这台计算机向各个处理器分派子任务，每一个处理器分配到当前观念清单的一个不同的子集。每个处理器有能力瞬间完成新观念与当前的子集的比较。在一次转换状态的时间内，处理器可以确定是否出现矛盾，然后转而处理下一个子集，这个时间是3×10–24秒（为了计算方便，把这个数近似设为10–23）。因此，每个处理器在一秒钟内可以进行1023次检验。在体积为一立方米的计算机内部，有1045个处理器。这台计算机每秒钟能处理1068次检验。
这个速度很快。面对一个由225个观念构成的清单，在一秒钟之内计算机就完成了所有需要进行的比较。
但是此后，进程突然慢下来了。在增加第226个观念时，花费1秒钟；检验第227个观念花费2秒钟；检验第232个观念大约需要1分钟。计算机的速度一如既往，但是清单中每增加一个观念，检验的工作量增加一倍。检验第250个观念需要一个多月。当清单扩展到300个观念时，需要的时间是——3 800万年！
没关系，这是一个思想实验，我们拥有世界上的全部时间。据估计宇宙的年龄大约是100亿年，折合成秒则在1017和1018之间。增加一或两个数量级，得到1019，这是对“永恒”的很恰当的估计。当宇宙的年龄达到现在的10倍时，所有恒星都将熄灭，生命很可能已经消亡。[7]因此，1019秒基本上是可以有意义地谈论的时间的最大值。如果一台理想计算机有1045个处理器，从时间的起点开始工作，直到时间的终点，它可以进行的检验次数是巨大的1019乘以1045的结果，也就是说，它可以把这么多个子集与新观念比较。这个数等于1087，足以处理一个由289个观念构成的清单。
我们需要一个更强大的计算机。一旦元件的最小尺寸已经确定，为了获得更强大的运算能力，唯有增加体积，把这台计算机扩大到占据一个房间、一座房屋……一个国家乃至于一个大陆那么大。但是无论如何扩大，其终极限度都不能超过宇宙的尺寸。
迄今已知的最遥远的类星体据估计在120亿~140亿光年以外。如果宇宙是有限的，一个大胆的估计是，其“直径”为1 000亿光年。1光年略少于1013千米，即1016米。因此，宇宙的直径大约是1027米，其体积大约是1081立方米。
因此，一台大小同宇宙一样的计算机可以有1045乘以1081个质子尺寸的元件，这个总数是10126。当然，这是白日做梦。关键在于：无论科技发达到什么程度，任何计算机的元件个数不会超过10126。大脑或任何形式的物理实体都不能超过这个限度。这是一个我们必须接受的极限。如果这样一台计算机从时间的起点开始工作，直到时间的终点，可以执行10126乘以1042次基本运算，即10168。
10168这个数字是你做任何事的次数的绝对极限。最接近超级任务的情况不过如此，因为人们没有足够的时间和空间去实现或超过10168次的任何事。不幸的是，运行10168次逻辑检验并不能前进很远。当清单扩展到包含大约558个观念时，这台计算机就报废了。
我们最多只能知道558件事吗？不，当然不是的。我们根据简单推理、三段论和连锁推理可以知道很多事情。558这个粗略的限制针对的是在逻辑上足够复杂、需要用指数时间算法来检验的观念。如果558个观念像卡洛尔猪排问题那样“不规则”，那么这些观念组成的集合很可能超出了计算机的处理能力——即使计算机和宇宙一样大。这就是新的悖论不断涌现的原因。
在逻辑上复杂的观念既不罕见，也非不自然。就连那些我们认为简单的观念（例如“所有乌鸦是黑色的”）实际上也配备了一系列的辅助性假设，可满足性的难度不仅限于逻辑谜题。
既然我们甚至不能辨别在我们的比较复杂的观念中是否包含矛盾，我们就没有完全理解它们。我们当然无法从这些观念推出所有可以推出的结论。如果你把逻辑推演当作观察世界的一个视域，那么这个视域是有限的。连锁推理是简单推理构成的链条，它构成了这个视域中的基本视线。通过这种视线，我们在黑暗中看得很远。对于更复杂的推理，我们则非常近视，无法看清所有东西，甚至无法看清所有蕴含在我们的思想实验中的东西。有些东西就摆在某个地方，但是我们永远也看不到。
如果说我们过于低能，无法理解那些我们没看到的东西，这种评价是不公平的。假如我们遇到了全知者（在关于悖论的讨论中全知者经常冒出来），全知者可以向我们指明我们没看到的东西，而我们有能力证明它们是真的。问题的答案是简单的——在你看到它以后。
这里的“我们”包括人类、计算机、宇宙生命以及一切物理机制。NP问题对于所有这些“我们”来说都是困难的。斯托克迈耶和迈耶的思想实验是奥尔贝斯悖论的一个信息时代的翻版。奥尔贝斯的出发点是我们能看见天空中的星星这个事实，而斯托克迈耶和迈耶的出发点是“整个宇宙不是一台计算机”这个事实。这里的结论是，这个宇宙中没有人无所不知。
[1] 原著出版时（1987年），苏联尚未解体，美苏两国军备竞赛正如火如荼地进行。——译者注
[2] 经作者同意，此处删掉了一个中国人不易理解的例子。——译者注
[3] “没有人知道连接这两个点的路线”这个要求是不必要的，出题者可以知道路线。出题者这样出题：自己在迷宫中随机地走过50个节点，记住自己走的路，定义他的起点为E点，终点为G点。仅把E和G告诉解题者，让解题者找到路线。从解题者的角度看，这道题的难度好比大海捞针；但是从出题者的角度看，这就像回家一样简单。——译者注
[4] 原文此处有笔误。译文已改。——译者注
[5] 指著名的迈克尔逊—莫雷实验，这个实验证实了爱因斯坦的光速不变理论。——译者注
[6] 这个例子不恰当。现代逻辑认为，“所有乌鸦都是黑色的”和“所有乌鸦都不是黑色的”并不矛盾，两个语句可以同时为真。不过，这并不影响作者的分析。——译者注
[7] 这个预言有一定的问题。宇宙的演化是新生和消亡并存的。不如说“到了那个时候，宇宙可能已经演化成与现在完全不同的形式”更合适一些。当然，这里所说的合适与否只是就本语句的语意而言，并不影响作者的逻辑结论。——编者注