1701742422
悖论意义重大、影响深远，超过了其表面看起来的程度。如果某人相信一些自相矛盾的观念，那么这些观点中至少有一些是他没有理由相信的。因而，理解一组观点（至少）意味着有能力发现观念中的矛盾。所以说，发现悖论的问题——即可满足性问题——是知识的界标。在试图全面理解某事的含义的过程中，已经内在地包含可满足性的难度。
1701742423
1701742424
在奠定牛顿的万有引力理论基础的因素中没有一样是古希腊人不知道的。疾病的细菌理论原本有可能提前几个世纪提出和确立——如果某人发现了正确的联系。同理，此刻一定也有我们尚未完成的综合，虽然所需的材料已经摆在面前。非常可能的是，解决“如何预防癌症”、“第10颗行星在哪儿”这些问题所需的全部事实已然齐备，但是还没有人发现组织这些事实的正确秩序。不仅如此，也许我们正在错过关于这个世界的各种各样的逻辑结论。这些结论有可能隐藏在我们见到、听到的每件事里，但是其复杂性有一点点超出了我们的理解力。
1701742425
1701742426
爱因斯坦写道：“全部科学的宏大目标是，从最小数量的假说或公理出发推导出最大数量的经验事实。”[4]把人类的全部经验加在一起，包括从冰川纪至今所有人曾经看到、摸到、听到、尝到或闻到的一切。从理论上说，这些信息可以汇集为一个巨大的目录，这个目录是一个简单的列表，对经验不做任何解释。对梦境、幻象、胡思乱想和错觉详尽描述，与“真实”的经验并列。二者中哪个是真实经验（如果有的话），留给目录的读者自己确定。
1701742427
1701742428
这个目录必然包含作为自然科学的基础的全部观察。对鸟、星星、蕨类植物、水晶和草履虫的全部观察都可以在目录中找到。这个目录也包含所有曾做过的科学实验中的那些哪怕最微小的细节。目录中还包括，在1887年那个特殊的日子，迈克尔逊和莫雷对下午稍晚时候的阳光照耀在仪器的镜子上的印象。[5]牛顿曾见过的所有苹果的颜色、尺寸、形状、运动速度以及加速度等信息也被搜集在目录中。
1701742429
1701742430
科学不是简单的经验目录。首先，任何人的大脑都无法容纳全部人类经验的整体。目录必须包括你经历过的一切，这就会占据迄今为止你的整个生命中的全部注意力！科学对人类经验（或经验的某些方面）进行压缩，达到一个可处理的形式。我们真正感兴趣的是理解目录所描述的这个世界。总的说来是这样，虽然某些特殊场合并非如此。在科学哲学中有一个恼人的问题：这种过程可能进行到何种程度？
1701742431
1701742432
每一个经验对未知的世界的某些部分的真值都做出了限制——和在逻辑谜题中一样。当然，未知事物间的关系可能非常微妙，每一个事物都必须用一系列的“如果”来限定。也许你的一个经验是：你听到你的朋友弗雷德说，他上个星期二见到了尼斯湖怪兽。经验的实际输入也许是这样：
1701742433
1701742434
如果弗雷德没犯错，他也没有撒谎，并且外部世界不是幻象，那么在星期二尼斯湖怪兽存在。
1701742435
1701742436
这些“如果”从句是必不可少的辅助性假设，它们使证实复杂化。
1701742437
1701742438
把经验目录输入一台超级计算机，编好程序，让它进行推演。这个任务只需要逻辑，而逻辑正是计算机的强项。在这个任务完成以后，计算机甚至可以把推演结果按重要性排序，重要的衡量标准是一个结果可以解释多少不同的经验。推演结果列表的第一条应当是人类可以知道的最重要的事实。
1701742439
1701742440
虽然以上介绍只是幻想，但是它确实展现了科学哲学中某些最核心的问题的基本框架。连锁推理是科学的基础，它的一致性可以在多项式时间内识别和检验。这些简单的逻辑问题相当于单行线迷宫（在每个节点处只有一或两条枝的迷宫），简单得不值一提，并且与“正常”的迷宫（每个节点处有三条或更多的枝）不同。更复杂的推演包括含有三或四个未知量的前提，解这类问题需要指数时间（实际上是无法完成的）。也许有一大类可以解释我们的感觉经验的逻辑推演是我们永远无法发现的。
1701742441
1701742442
把我们的经验设想为迷宫，把关于经验的逻辑真理设想为遍布迷宫的路径。可满足性问题的NP完全性表明，我们永远无法穷尽所有的潜在路线。
1701742443
1701742445
和宇宙一样大的计算机
1701742446
1701742447
计算机科学家拉里·J·斯托克迈耶（Larry J. Stockmeyer）和阿尔伯特·r·迈耶（Albert R. Meyer）设想了一台大小和宇宙一样的计算机，以此来形象地展示处理NP问题的极高难度。他们表明，我们在想回答许多关于宇宙的问题时，会发现宇宙并不够大。
1701742448
1701742449
假定我们试图把所有已接受的观念列成一个清单。就像笛卡儿一样，我们希望从一片空白开始，并且非常小心地把观念填进去。在任何一个观念被填进去之前，首先再次检查已经被列进清单的观念，以确保增加的新观念与已有的观念不产生矛盾。这个检验即为可满足性问题。
1701742450
1701742451
也许你会认为，为此只需要把清单浏览一遍，确保准备加入的新观念不与任何一个以前列入的观念直接矛盾。然而，实际情况没有这么简单。
1701742452
1701742453
显然，新的观念有可能与旧的观念矛盾。如果新的观念是“所有乌鸦都是黑色的”，而旧观念中有一条“所有乌鸦都不是黑色的”，在这里你就遇到了矛盾。[6]最危险的是这种情况：三个或更多命题，各自独立地看都是可以成立的，但是合在一起构成矛盾。通常，“悖论”这个术语专门指这种情况，矛盾不是一目了然的。
1701742454
1701742455
假定新的观念是“所有草都是绿色的”，清单中可能已经包含了两个语句：
1701742456
1701742457
所有干草都是黄色的。
1701742458
1701742459
干草是草。
1701742460
1701742461
这两个语句若加上新语句就产生了矛盾。如果你仅仅一对一对地检查——在三个语句中拿出两个来检查是否相互一致，你就会遗漏这个矛盾。为了排除这种情况，有必要在清单中一对一对地取出所有可能的命题组合，一一检验它们加入新命题后是否一致。这极大地增加了检查的工作量。但是这还不算完。也许还有更精致的悖论，只在四个、五个或更多命题合在一起考虑时才显现出来。在100万个观念中加入一个观念，即使在原来的观念中任意取出999 999个观念与新观念合在一起都是一致的，整体上还是有可能出现矛盾。
1701742462
1701742463
需要检查的事实太多了，显然必须借助于计算机。我们从l号观念开始（这个观念也许是“我思故我在”）。为了让计算机能够处理，这个观念被表示为关于布尔未知量的一个逻辑命题，下一步，我们准备加入一个新的观念，2号观念。我们指示计算机对照1号观念进行检查，看看是否出现矛盾。此时，只需一次逻辑检验（比照2号观念和1号观念）。
1701742464
1701742465
现在，清单中有两个观念，我们准备加入第三个。此时必须进行三次检验：与1号观念比照；与2号观念比照；与1号、2号合在一起比照。
1701742466
1701742467
第四个观念必须和7个命题集合进行比照：分别与1、2、3号比照；分别与1和2、1和3、2和3比照；与l、2、3合在一起比照。
1701742468
1701742469
事实上，一个新的观念必须与当前清单上的所有可能子集合在一起检验。n件东西的子集数计算公式是一个指数函数：2n。这个公式把空集也计算在内，其实我们不必考虑空集。非空子集的数量是2n–1。
1701742470
1701742471
假定这些观念（或其中的某些信息）在逻辑上足够复杂，因而无法避免指数时间的算法。此时，需要进行比较的次数如下表：
[
上一页 ]
[ :1.701742422e+09 ]
[
下一页 ]